Bale Share

Interview

Time limit1sMemory limit128 MB

Summary

Assign N bales (N up to 20) to three barns so the largest barn total is as small as possible, and print that smallest possible largest total.

Level: Medium4 of 10
Topics: Brute force, Recursion, Backtracking, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
8
14
2
5
15
8
9
20
4
```
Expected output
```
26
```
Example 2
Input
```
3
5
5
5
```
Expected output
```
5
```