Kile và Pogi nhặt được ~N~ tờ tiền trên đường. Sau khi chắc chắn không thể tìm thấy chủ nhân của số tiền trên, họ quyết định chia những tờ tiền với nhau sao cho tổng số tiền mà mỗi người nhận được là như nhau. Tất nhiên, tổng giá trị của những tờ tiền bị dư ra phải là nhỏ nhất có thể.

Bởi vì họ không thể đặt lại những tờ tiền bị dư ra về chỗ cũ, họ quyết định ghé vào một sòng bạc gần đó và đặt cược toàn bộ số tiền bị dư ra với hi vọng nhận được gấp đôi số tiền đã đặt cược. Vận may mỉm cười khi máy đánh bạc (slot machine) ra số 777 và họ quyết định chia đôi số tiền thắng cuộc. Sòng bạc sẽ luôn thanh toán sao cho Kile và Pogi có thể chia số tiền họ vừa thắng thành hai phần bằng nhau.

Với sự phấn khích tột độ, hai chàng trai đã đánh mất khả năng toán học của mình. Hãy giúp họ tính số tiền mỗi người sẽ nhận được nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \leq N \leq 500)~, số lượng tờ tiền trên đường.

Mỗi dòng trong số ~N~ dòng tiếp theo chứa một số nguyên dường ~c_i~ là giá trị của tờ tiền thứ ~i~. Tổng giá trị của những tờ tiền không quá ~100\:000~.

Output

Một giá trị duy nhất là số tiền mỗi người sẽ nhận được.

Subtask

• ~10~ test có ~N \leq 13~.
• ~4~ test có ~N \leq 50~ và tổng giá trị của những tờ tiền không quá ~1000~.
• ~6~ test còn lại không có ràng buộc gì thêm.

Sample 1

Input

4
2
3
1
6

Output

6

Giải thích

Kile sẽ lấy tờ tiền với giá trị ~2~, ~3~, và ~1~. Pogi sẽ lấy tờ tiền với giá trị ~6~.

Sample 2

Input

5
2
3
5
8
13

Output

18

Giải thích

Kile sẽ lấy tờ tiền với giá trị ~5~ và ~8~. Pogi sẽ lấy tờ tiền với giá trị ~13~. Tờ tiền bị dư ra với giá trị ~2~ và ~3~ sẽ được "gấp đôi" trong sòng bạc. Do đó, số tiền mỗi người nhận được là ~13+5=18~