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(1\le n\le 500)$ — the number of banknotes in the wallet. Each of the following lines contains one positive integer value $c_i$ — the value of the $i$-th banknote (in manats). It is known that $c_1+...+c_n\le 10^5$.

Output

Print the amount of money that Huseyn got.

Examples

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.