Chuyện kể lại rằng, trong một lần thám hiểm hang động, Aladdin và thần đèn phát hiện một kho báu cổ xưa gồm ~N~ thỏi vàng ròng. Vẫn còn tiếc rẻ vì ngày trước ở trong hang thần không thó được món gì ngoài cây đèn cũ nát, Aladdin quyết tâm lần này sẽ mang hết vàng về. Ngặt nỗi kho báu này bị nguyền : nếu muốn đem ~K~ thỏi vàng ra khỏi hang thì ~K~ thỏi vàng này phải được chia thành ~2~ phần có khối lượng bằng nhau mà không được cắt, đập thỏi vàng nào ra cả. Nếu không làm đúng thì hang sẽ sập xuống chôn vùi tất cả, đến thần đèn cũng không cứu được.

Thần đèn dù tài phép vô biên nhưng tính toán lại rất kém, chỉ có thể hô biến ra một cái cân ký chứ không chọn được vàng. Aladdin cũng không hơn gì (lớn lên trên đường phố mà). Tuy nhiên Aladdin lại không chịu ra khỏi hang một khi chưa đem được lượng vàng nhiều nhất về. Thần đèn đang ngán ngẩm không biết khi nào Aladdin mới chọn vàng xong thì khỉ Abu xuất hiện. Nhanh như thoắt Abu đã chọn xong vàng và chia thành ~2~ túi có khối lượng đúng bằng nhau. Abu lại còn chọn được lượng vàng nhiều nhất nữa. Trong lúc Aladdin mừng hớn hở (vì bắt được vàng) thì thần đèn do chậm hiểu vẫn còn thắc mắc không biết một túi có bao nhiêu vàng. Hãy giúp thần đèn tìm con số này.

Input

Dòng đầu ghi số ~N~ là số thỏi vàng trong kho báu.

~N~ dòng tiếp theo, dòng thứ ~i~ ghi số nguyên dương ~M_i~ là khối lượng của thỏi vàng ~i~ (tính theo gam).

Output

Ghi ra một số nguyên duy nhất là số gam vàng trong một túi của Abu.

Giới hạn

~2 \leq N \leq 24~.

~1 \leq M_i \leq 40 \times 10^6~.

Sample Input

5
6000
30000
3000
11000
3000

Sample Output

6000