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$