Kile and Pogi have found ~N~ banknotes on the street. After making sure that the original owner is nowhere to be found, they decided to split the banknotes amongst themselves. In the end they want to "win" the same amount of money so they split the banknotes in such a way. Of course, the sum of the banknotes nobody ends up having is the least possible one.

Since they couldn't just leave the remaining banknotes on the street, they decided to go to a nearby casino and put everything on red, hoping that they would end up getting twice the money they bet. The roulette decided on the (lucky, for this time) number ~13~ and our heroes decided to split the money they won. The payout is such that Kile and Pogi will always be able to split the money they won into two equal parts.

Because of the immense adrenaline rush, the boys have lost their mathematical abilities. Help them figure out how much money each of them is taking home.

Input Specification

The first line of input contains the integer ~N~ ~(1 \leq N \leq 500)~ that denotes the number of banknotes on the street.

Each of the following ~N~ lines contains a single positive integer ~c_i~ that denotes the value of the ~i^\text{th}~ banknote in kunas (kn). The total sum of money will not exceed ~100\,000~ kn.

Output Specification

You must output the amount of money each of them took home.

Scoring

In test cases worth ~50~ points total, ~N~ will be less than or equal to ~13~.

In test cases worth ~70~ points total, ~N~ will be less than or equal to ~50~, and the total sum of money will be at most ~1\,000~ kn.

Sample Input 1

4
2
3
1
6

Sample Output 1

6

Explanation for Sample Output 1

Kile took banknotes worth ~2~, ~3~ and ~1~ kn, and Pogi took the banknote worth ~6~ kn.

Sample Input 2

5
2
3
5
8
13

Sample Output 2

18

Explanation for Sample Output 2

Kile took the banknotes worth ~5~ and ~8~ kn, and Pogi took the banknote worth ~13~ kn. The remaining banknotes are worth ~2~ and ~3~ kn, which the boys have "doubled" in the casino. The total earnings of each of them is ~13 + 5 = 18~ kn.