이혼

잭과 질이 이혼하면서 두 사람이 함께 모은 재산을 공평하게 나누려고 한다. 두 사람이 함께 소유한 집은 모두 $N$채이며, 각 집의 가치는 1,000,000달러 이상 40,000,000달러 이하이다.

잭이 몇 채의 집을 가져가고, 질도 몇 채의 집을 가져간다. 잭이 가져가는 집들의 가치의 합은 질이 가져가는 집들의 가치의 합과 반드시 같아야 한다. 두 사람이 가져가지 않고 남은 집은 모두 판다.

이렇게 공평하게 나누는 방법이 여러 가지라면, 두 사람이 각자 가져가는 가치의 합(서로 같은 값)이 가장 커지도록 나눈다. 다시 말해, 팔아야 하는 집의 가치의 합이 가장 작아지도록 나눈다.

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

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 집의 수 $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달러짜리 집 두 채를 가져가면, 두 사람이 가져가는 가치의 합이 각각 6,000,000달러로 같아져 공평하게 나눌 수 있다. 이때 남는 두 집(11,000,000달러와 30,000,000달러)을 팔며, 그 가치의 합은 41,000,000달러이다.