Когда-то весы и гири, которые сегодня почти не используются, имели очень широкое распространение.

Когда на обе чаши весов помещаются одинаковые массы, они остаются в равновесии. Так мы знаем, что масса на обеих чашах одинакова. Так можно измерять разные массы с помощью гирь, массы которых заранее известны. Представьте, что у Вас есть такие весы, а также 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) - массы гирь.

Выходные данные

Выведите наименьшую массу, которую нельзя измерить с помощью весов и имеющихся гирь.