Problem Description

Kile and Pogi found $N$ banknotes on the road. Each of them will take some banknotes so that the total amount each person gets is the same. At the same time, they want this total amount to be as large as possible.

Next, they will take the remaining banknotes to a casino. Because they are very lucky, after using the remaining amount as a bet, they will get double that amount. Then, they will split the obtained money equally again and add it to each person’s total amount.

Find the total amount of money each person can get.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain a positive integer $c_i$, representing the value of the $i$-th banknote. It is guaranteed that the total value of all $N$ banknotes does not exceed $10^5$.

Output Format

Output the total amount of money each person can get.

4
2
3
1
6

6

5
2
3
5
8
13

18

Hint

[Sample 1 Explanation]

Kile can choose the banknotes with values $2,3,1$, and Pogi can choose the banknote with value $6$. Since there are no remaining banknotes, the total amount each person gets is $6$.

[Sample 2 Explanation]

Kile can choose the banknotes with values $5,8$, and Pogi can choose the banknote with value $13$. The remaining banknotes have values $2,3$, so after going to the casino, the total amount each person gets is $13+2+3=18$.

[Constraints]

For $50\%$ of the testdata, $N \le 13$.

For $70\%$ of the testdata, $N \le 50$, $\sum c_i \le 1000$.

For $100\%$ of the testdata, $1 \le N \le 500$.

[Notes and Explanation]

This problem is translated from COCI 2016-2017 CONTEST #4 T3 Kas.

The score of this problem follows the original COCI settings, with a full score of $100$.

Translated by ChatGPT 5