Description

FJ has $n$ hay bales, and the weight of the $i$-th bale is $s_i$. He wants to distribute the hay as evenly as possible among three farms.

He wants the maximum total weight after distribution to be as small as possible. For example, let $b_1, b_2, b_3$ be the total weights assigned to the three farms after distribution. Assume $b_1 \ge b_2 \ge b_3$. He wants the value of $b_1$ to be as small as possible.

Please compute the minimal possible value of $b_1$.

Input Format

The first line contains a positive integer $n$.
Each of the next $n$ lines contains a positive integer representing a weight.

Output Format

Output a single line containing one integer, the answer.

8 
14 
2 
5 
15 
8 
9 
20 
4 

26 

Hint

[Sample Explanation]
One valid distribution is:
Farm 1: $2,9,15$, $b_1 = 26$.
Farm 2: $4,8,14$, $b_2 = 26$.
Farm 3: $5,20$, $b_3 = 25$.

Constraints
For $100\%$ of the testdata, $1 \le n \le 20$, $1 \le s_i \le 100$.

Translated by ChatGPT 5