Giải bài trực tuyến

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ỉ Abuxuấ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 – 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).

         Giới hạn :        2 <= N <= 24

                              1 <= M_i<= 40x10⁶

Output

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

Example

Input:
5
6000
30000
3000
11000
3000

Output:

6000