Problem Description
What are you guys playing?
I’m supposed to be playing Game Of War™ but this one player keeps kicking my ass.
Is it TheLegend27?!
Yeah, TheLegend27.
Who is the legend 27?
Some say TheLegend27 is the first Game Of War™ player ever.
Born from fire.
TheLegend27 Backstory
TheLegend27 has robbed the bank with TheJianzhi22, obtaining N banknotes with values Ai . They want to split the money equally among themselves, such that the least amount of money is left behind.
They gambled the money which cannot be split, and managed to double the amount of money obtained! They then proceed to split the doubled money equally.
TheLegend27 only good at playing Game of War™ and has asked TheJianzhi22 calculate the amount of money each person obtains. Help TheJianzhi22 before he too gets destroyed by TheLegend27!
Limits
All variables are positive integers.
Subtask 1 (11%): N ≤ 13, Total value of banknotes ≤ 100000.
Subtask 2 (28%): N ≤ 50, Total value of banknotes ≤ 1000.
Subtask 3 (61%): N ≤ 500, Total value of banknotes ≤ 100000.
Subtask 4 (0%): Sample Testcases.
Input
The first line of input will contain one integer, N.
The next N lines of input will contain 1 integer each, representing Ai.
Output
Output the amount of money each person obtains.
Sample Testcase 1
Input
4
2
3
1
6
Output
6
Explanation
TheLegend27 takes banknotes with values {2, 3, 1} and TheJianzhi22 takes banknotes with value(s) {6}.
Sample Testcase 2
Input
5
2
3
5
8
13
Output
18
Explanation
TheLegend27 takes banknotes with values {5, 8} and TheJianzhi22 takes banknotes with value(s) {13}. The rest of the banknotes is doubled, so they both get {2, 3}.