Banknotes and Roulette

Kile and Pogi found $N$ banknotes on the street. After making sure that the owner was nowhere to be found, they decided to split the banknotes between themselves.

Both of them want to end up with the same amount, so they split the banknotes into two groups of equal total value. Among all such splits they choose one where the total value of the banknotes nobody takes is as small as possible.

They could not leave the remaining banknotes on the street, so they went to a nearby casino and bet all of that money on red. The roulette stopped on 13, and this time the bet won. The casino pays out twice the amount that was bet. The payout is always an even number of kuna, so the two of them split it into two equal halves.

Print how much money each of them takes home.

The first line contains the number of banknotes $N$ ($1 \le N \le 500$).

Each of the next $N$ lines contains one positive integer $c_i$, the value of the $i$-th banknote in kuna (kn). The total value of all banknotes does not exceed $100000$.

Print one integer, the amount of money each of them takes home.

In the first example Kile takes the banknotes worth 2 kn, 3 kn and 1 kn, and Pogi takes the banknote worth 6 kn. Nothing is left over, so the casino pays nothing and each of them takes home 6 kn.

In the second example one of them takes the 13 kn banknote and the other takes the banknotes worth 2 kn, 3 kn and 8 kn, so both hold 13 kn. The 5 kn banknote is left over and the casino pays 10 kn, so each of them receives 5 kn more and takes home 18 kn.