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