Stannis borathean is attacking kings landing from three gates.To defend the city Tyrion again comes up with a fair solution. Tyrion has N soldier troops with given strengths. Tyrion wants to divide army into 3 sets such that the sum of strengths in these three sets are as equal as possible. In other words he wants to make three sums \(S1, S2\) and \(S3\) using all troops with constraint that \(S1\) ≥ \(S2\) ≥ \(S3\) and \(S1\) is as less as possible.

Input
Input contains integer N which is number of troops followed by N lines. Each line contains an integer, strength of one of the troop.

Output
Strength of strongest set that is sum \(S1\).

Constraints:
1 ≤ N ≤ \(12\)
1 ≤ Strength of each troop ≤ \(100\)