eolymp
Competitions

Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29

Distributing the Money

Huseyn and his younger brother found a wallet with n banknotes on the street. Since the owner of the money could not be found, they decided to divide the money among themselves. They divided the money among themselves so that everyone got the same amount of money. At this time, there could be the least amount of money that could be left. Huseyn took this money because he is the older brother.

Determine the amount of money that Hussein got.

Input

The first line contains an integer n (1n500) - the number of banknotes in the wallet. Each of the following lines contains one positive integer value ci - the value of the i-th banknote (in manats). It is known that c1 + ... + cn105.

Output

Print the amount of money that Huseyn got.

Explanation

Example 1. Huseyn can take the banknote of 10 manats, and his brother can take the rest of the banknotes.

Example 2. In the initial hand, Huseyn can take a banknote of 19 manats, and his brother can take a banknote of 17 manats and 2 manats. In this case, a banknote with value of 3 manats goes to Huseyn. Thus, Huseyn receives 19 + 3 = 22 manats.

Time limit 1 second
Memory limit 512 MiB
Input example #1
5
4
2
3
1
10
Output example #1
10
Input example #2
4
3
17
2
19
Output example #2
22
Source Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29