This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.


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?


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.


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

Sample Input 1

1 2 3 2

Sample Output 1


Sample Input 2

3 4 5 4 9 8

Sample Output 2



not here yet