Lucky Split

Kile and Pogi found N banknotes on the road. They want to pick some of the banknotes to split between themselves so that each gets the same total amount. Moreover, they want the divided amount to be as "safe" as possible – that is, they want to secure the smallest possible amount in this fair division so as to leave more for the casino. After the initial division, they take the remaining banknotes to a casino. Thanks to their luck, the money they bet is doubled. They then split the doubled amount equally and add it to their initially secured amount.

More formally, let the total sum of the banknotes be T. They choose two nonempty disjoint subsets X and Y (with X ∪ Y being some subset of the banknotes) such that sum(X)=sum(Y)=K. The leftover amount is T-2K, which after doubling becomes 2(T-2K) and split evenly gives each T-2K. Hence every one ends up with

They want the final amount (and thus each person’s share) to be as large as possible. Since T is fixed, maximizing T-K is equivalent to minimizing K over all possible choices of nonempty disjoint subsets X and Y with equal sum. If no such partition exists the pair will go to the casino with all banknotes, and each will get T after splitting the doubled total.

Given the value on each banknote, compute the maximum amount each person can finally obtain.

Note: A banknote cannot be split. The two subsets used in the fair division must be nonempty and must not share any banknote.

inputFormat

The first line contains an integer N, the number of banknotes. The second line contains N space‐separated positive integers representing the values on the banknotes.

outputFormat

Output a single integer — the maximum amount each person can finally obtain following the procedure described above.

sample

3
1 2 3

3