Same Towers

Hongjun has N rectangular blocks. He can build a tower by stacking blocks on top of one another.

He wants to build two towers with the same height. Each tower must contain at least one block. He wants this common height to be as large as possible, and he does not have to use every block.

Given the height of each block, compute the maximum possible height of the two equal towers.

The first line contains the number of blocks N. N is a positive integer not greater than 50.

The second line contains the height of each block. Each height is a positive integer not greater than 500,000, and the sum of all block heights does not exceed 500,000.

Output the maximum possible equal tower height.

If it is impossible to build two nonempty towers with the same height, output -1.