
Колись ваги та гирі, які сьогодні майже не використовуються, мали дуже широке розповсюдження.
Коли на обидві чаші вагів поміщаються однакові маси, вони залишаються в рівновазі. Це дозволяє визначити, що маси на обох чашах однакові. Таким чином, можна вимірювати різні маси за допомогою гир, маси яких заздалегідь відомі. Уявіть, що у вас є такі ваги, а також гир з цілими масами. Яка найменша маса, яку не можна виміряти за допомогою цих вагів і гир?
Наприклад, у вас є гирі з масами , , і кг. Зважити кг можна, помістивши одну з -кілограмових гир на одну чашу вагів. Зважити кг можна, помістивши дві -кілограмові гирі на одну чашу вагів. кг можна зважити, помістивши -кілограмову гирю на одну чашу вагів і -кілограмову гирю на іншу чашу вагів. Найменша маса, яку не можна виміряти в даному прикладі, дорівнює кг.
У першому рядку записано одне ціле число (1 \le n \le 16) - кількість гир для зважування. У другому рядку записано цілих чисел w_1, w_2, ..., w_n (1 \le w_i \le 10^8) - маси гир.
Виведіть найменшу масу, яку не можна виміряти за допомогою вагів і наявних гир.
Приклад 1
Приклад 2
Приклад 3
Приклад 4