Bale Share

Farmer John has just received a new shipment of $N$ ($1 \le N \le 20$) bales of hay, where bale $i$ has size $S_i$ ($1 \le S_i \le 100$). He wants to divide the bales among his three barns as fairly as possible.

Farmer John decides that a fair division is one that makes the largest share as small as possible. Formally, if $B_1$, $B_2$, and $B_3$ are the total sizes of the bales placed in barns 1, 2, and 3 respectively, ordered so that $B_1 \ge B_2 \ge B_3$, then he wants $B_1$ to be as small as possible.

Each bale cannot be split and must be placed in exactly one barn. A barn may be left empty (total size 0).

Determine the value of $B_1$ in a fair division.

The first line contains the number of bales, $N$.

Each of the next $N$ lines contains one integer: the $i$-th of these lines gives $S_i$, the size of the $i$-th bale.

Print the value of $B_1$ in a fair division on a single line.