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.
The first line contains an integer n (1≤n≤500) — 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+...+cn≤105.
Print the amount of money that Huseyn got.
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.