이혼

잭과 질은 이혼을 하게 되었고, 두 사람은 재산을 공평하게 나누려고 한다. 두 사람은 집을 N채 가지고 있고, 각 집의 가치는 1,000,000달러 보다 크거나 같고, 40,000,000보다 작거나 같다. 잭은 일부 집을 가져가고, 질도 일부 집을 가져간다. 남은 집은 판다.

잭이 가져가는 집의 가치의 합은 질의 합과 같아야 한다. 공평하게 나누는 경우가 여러 가지라면, 각 사람이 가진 집의 가치의 합을 가장 크게 하려고 한다.

집 N채의 가치가 주어졌을 때, 팔아야 하는 집의 가치를 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 집의 수 N이 주어진다. 집의 수는 24개를 넘지 않는다. 다음 N개 줄에는 집의 가치가 주어진다.

입력의 마지막 줄에는 0이 주어진다.

각 테스트 케이스마다, 집을 공평하게 나누기 위해 팔아야 하는 집의 가치를 출력한다.

문제의 예제는 잭과 질이 가지고 있는 집 5채의 가치가 6,000,000, 30,000,000, 3,000,000, 11,000,000, 3,000,000인 경우이다. 잭이 6,000,000 달러 집, 질이 3,000,000 달러 집 두 개를 가져가면 두 사람은 공평하게 집을 나눌 수 있다. 남는 집 (11,000,000 달러, 30,000,000 달러) 의 합은 41,000,000 달러이다.