

IX Olimpiada Informatyczna 2001/2002

Task: wag

Author: Krzysztof Onak

Balance
We have a balance at our disposal. The scales are in balance if and
only if both pans are empty or the weights on each pan weigh the same
in total. In the given set of weights one should find such two
disjoint subsets that, after putting all the weights of one on one pan
and all the weights of the other on the other pan, the scales are in
balance. Moreover, we require to put on the scales the heaviest weight
possible.
Task
Write a program which:
 reads from the text file wag.in the weights of the
available weights,
 selects two disjoint sets of the weights meeting the conditions of
the task,
 writes the result to the text file wag.out.
Input
In the first line of the text file wag.in there is one
integer n, 2<=n<=1 000, equal to the number
available weights. In each of the following n lines there is
one positive integer being the weight of one weight from the set of
available weights. You may assume that all the weights weigh at most
50 000 in total.
Output
In the first line of the text file wag.out you should write
heaviest weight of thing.
Example
For the following input file wag.in:
4
1
1
2
7
a correct answer is in the following output file wag.out:
2
Announcement during the Contest
From all the arrangements of the weights, for which the scales keep
balance, one should choose that one which contains the heaviest weight
possible.
