Tərəzi

Bir zamanlar, günümüzdə demək olar ki, istifadə edilməyən, şəkildə gördüyünüz tərəzi və çəki daşları çox geniş istifadə edilirdi.

Bu tərəzinin hər iki gözünə bərabər kütlələr qoyulduqda o balansda qalır və bunun nəticəsində tərəzinin hər iki gözündəki kütlənin eyni olduğunu bilirik. Beləcə, əvvəlcədən kütlələri bilinən çəki daşlarının köməyi ilə müxtəlif kütlələri ölçmək mümkündür.

Təsəvvür edin ki, belə bir tərəziniz və n sayda tam kütləli çəki daşınız var. Bu tərəzidən və daşlardan istifadə etməklə hansı ən kiçik tam kütləni ölçmək mümkün deyil?

Məsələn, 4 ədəd çəki daşınızın olduğunu düşünək. Onların kütlələri 1, 1, 4 və 15 kq olsun. Bu zaman tərəzinin bir gözünə 1 kq lıq daşlardan birini qoymaqla 1 kq ı, iki ədəd 1 kq lıq daşları qoymaqla 2 kq ı, bir gözünə 1 kq lıq, digər gözünə 4 kq lıq daş qoymaqla 3 kq ı ölçə bilərik. Bu nümunədə ölçmək mümkün olmayan ən kiçik tam kütlə 7 kq dır.

Giriş verilənləri

Birinci sətirdə bir tam ədəd, n (1 ≤ n ≤ 16) çəki daşlarının sayı, növbəti sətirdə boşluqla ayrılmış n sayda tam ədəd w[1], w[2], ..., w[n] (1 ≤ w[i] ≤ 10^8) daşların kütlələri verilir.

Çıxış verilənləri

Çıxışa tərəzidən və daşlardan istifadə etməklə ölçmək mümkün olmayan ən kiçik tam kütləni verin.