Problem C: Celebrity Split
Jack and Jill have decided to
separate and divide their property equally.
Each of their N mansions has a value between
1,000,000 and 40,000,000 dollars.
Jack will receive some of the mansions;
Jill will receive some of the mansions;
the remaining mansions will be sold, and
the proceeds split equally.
Neither Jack nor Jill can tolerate the other
receiving property with higher total value.
The sum of the values of the mansions Jack
receives must be equal to the sum of the values
of the mansions Jill receives. So long as
the value that each receives is equal,
Jack and Jill would like each to
receive property of the highest possible value.
Given the values of N mansions,
compute the value of the mansions
that must be sold so that the rest may be divided
so as to satisfy Jack and Jill.
Example
Suppose Jack and Jill own 5 mansions valued at
6,000,000, 30,000,000, 3,000,000, 11,000,000, and 3,000,000
dollars. To satisfy their requirements, Jack or Jill would
receive the mansion worth 6,000,000 and the other would receive
both manstions worth 3,000,000 dollars. The mansions worth
11,000,000 and 30,000,000 dollars would be sold, for a total
of 41,000,000 dollars. The answer is therefore
41000000.
Input Specification
The input consists of a sequence of test cases.
The first line of each test case contains a single integer N,
the number of mansions, which will be no more than 24.
This line is followed by N lines, each giving the value
of a mansion.
The final line of input contains the integer zero. This line is not
a test case and should not be processed.
Sample Input
5
6000000
30000000
3000000
11000000
3000000
0
Output Specification
For each test case, output a line containing a single integer,
the value of the mansions
that must be sold so that the rest may be divided
so as to satisfy Jack and Jill.
Output for Sample Input
41000000
Gordon Cormack