P3040 [USACO12JAN] Bale Share S

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$.

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

Output a single line containing one integer, the answer.

[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