Problem

After your successful efforts in timing the alien invasion, Flatland has emerged victorious! $N$ of the alien ships have been salvaged and the Flatlanders want to use them to build not one, not two, but three tall statues commemorating this independence day!

Each of the alien ships has it’s own length. The Flatlanders line these ships up on end to form three stacks. In order to create a balanced visual piece, they would like to minimize the length of the longest statue. Can you help them determine the minimum height of the longest statue?

Input

Each test case begins with an integer $N (1 \leq N \leq 50)$. The next line contains $N$ integers $H_i (1 \leq H_i \leq 50)$, representing the lengths of the ships.

For $40\%$ of the points, $M \leq 10,000$.

Output

For each test case, output one integer: the minimum length of the longest statue.

Sample Input 1

4
1 2 3 2

Sample Output 1

3

Sample Input 2

6
3 4 5 4 9 8

Sample Output 2

12

Editorial

not here yet