#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 has robbed the bank with TheJianzhi22, obtaining *N* banknotes with values *A _{i}* . 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 *A _{i}*.

## 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}.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 11 | 12 | 1s | 256MB | Minimum |

2 | 28 | 6 | 1s | 256MB | Minimum |

3 | 61 | 8 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o robbery -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512