Banknotes and Roulette

Interview

Time limit2sMemory limit512 MB

Summary

Split banknotes so the two equal-sum groups leave the smallest leftover, then add half of twice that leftover to each person's total.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Prefix sum, Greedy
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Hint

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.

Examples2

Example 1
Input
```
4
2
3
1
6
```
Expected output
```
6
```
Example 2
Input
```
5
2
3
5
8
13
```
Expected output
```
18
```