Весы
Когда-то весы и гири, которые сегодня почти не используются, имели очень широкое распространение.
Когда на обе чаши весов помещаются одинаковые массы, они остаются в равновесии. Так мы знаем, что масса на обеих чашах одинакова. Так можно измерять разные массы с помощью гирь, массы которых заранее известны. Представьте, что у Вас есть такие весы, а также n гирь с целочисленными массами. Чему равна наименьшая масса, которую нельзя измерить с помощью этих весов и гирь?
Пусть у Вас имеются 4 гири с массами 1, 1, 4 и 15 кг. Взвесить 1 кг можно, поместив одну из 1-килограммовых гирь на одну чашу весов. Взвесить 2 кг можно, поместив две 1 -килограммовые гири на одну чашу весов. 3 кг можно взвесить, поместив 1-килограммовую гирю на одну чашу весов и 4-килограммовую гирю на другую чашу весов. Наименьшая масса, которую нельзя измерить в данном примере, равна 7 кг.
Входные данные
В первой строке записано одно целое число n (1 ≤ n ≤ 16) - количество гирь для взвешивания. Во второй строке записано n целых чисел w[1], w[2], ..., w[n] (1 ≤ w[i] ≤ 10^8) - массы гирь.
Выходные данные
Выведите наименьшую массу, которую нельзя измерить с помощью весов и имеющихся гирь.