Divorce

Jack and Jill are getting divorced and want to split the property they built together fairly. Together they own $N$ houses, and the value of each house is at least 1,000,000 dollars and at most 40,000,000 dollars.

Jack takes some of the houses and Jill takes some of the houses. The total value of the houses Jack takes must be exactly equal to the total value of the houses Jill takes. Every house that neither of them takes is sold.

If there are several fair ways to split the property, they choose the one that makes the value each person receives (the two values are equal) as large as possible. In other words, they make the total value of the houses that must be sold as small as possible.

Given the values of the $N$ houses, write a program that computes the total value of the houses that must be sold.

The input consists of several test cases. The first line of each test case contains the number of houses $N$, where $N$ is at most 24. Each of the next $N$ lines contains the value of one house.

The last line of the input contains a single 0, which marks the end of the input.

For each test case, print on its own line the total value of the houses that must be sold in order to split the property fairly.

For example, suppose the five houses are worth 6,000,000, 30,000,000, 3,000,000, 11,000,000, and 3,000,000 dollars. If Jack takes the house worth 6,000,000 dollars and Jill takes the two houses worth 3,000,000 dollars each, then each of them receives houses worth 6,000,000 dollars in total, so the property is split fairly. The two remaining houses (worth 11,000,000 and 30,000,000 dollars) are sold, and their total value is 41,000,000 dollars.