0215. Trojan Towers

Имя входного файла: e.in
Имя выходного файла: e.out
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

After terrible accident of 11th September in USA, The President has come to a conclusion of rebuilding the former American pride in a little different form. He decided to build three towers instead of two so probably terrorists will get puzzled which tower to strike first (two towers were too few for such a decision) and he will name them Trojan Towers to even more scare those hackers who probably controlled the planes. For even more edification he decided to build those towers using some or all of the blocks remained from the previous Twin Towers. Only foundation of each of the three towers will be built anew. Of course, Trojan Towers should be as high as possible and should be equal in their heights. However, their structure can be different due to different blocks used to construct them.

Input file

The first line contains the only number N - the number of blocks available. 0 ≤ N ≤ 100. The next line contains N integers; each integer denotes the height of a particular block to be used in Trojan Towers construction. The sum of all heights will not exceed 300.

Output file

Output a single integer - the maximum height of Trojan Towers (meaning height of each one, not their total height). Remember that foundation for all three towers will be built anyway, so zero is also an acceptable equal height as soon as it is maximally possible.

Example:

e.ine.out
7 1 1 1 1 2 2 4 4


Источник: Petrozavodsk Winter 2004. Denis Koshman Contest, Saturday, January 31
Автор: Denis Koshman

Обсудить       Отправить решение



Версия для печати