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