시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
30 초 128 MB 53 13 10 40.000%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

5
6000000
30000000
3000000
11000000
3000000
0

예제 출력 1

41000000

힌트

문제의 예제는 잭과 질이 가지고 있는 집 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 달러이다.

W3sicHJvYmxlbV9pZCI6IjQxNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWQ2M2MiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZGl2b3JjZS5qcGdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjY5cHg7IHdpZHRoOjI2OXB4XCIgXC8+XHVjN2FkXHVhY2ZjIFx1YzljOFx1Yzc0MCBcdWM3NzRcdWQ2M2NcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YWNlMCwgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM3YWNcdWMwYjBcdWM3NDQgXHVhY2Y1XHVkM2M5XHVkNTU4XHVhYzhjIFx1YjA5OFx1YjIwNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjOWQxXHVjNzQ0IE5cdWNjNDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzlkMVx1Yzc1OCBcdWFjMDBcdWNlNThcdWIyOTQgMSwwMDAsMDAwXHViMmVjXHViN2VjIFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA0MCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YzdhZFx1Yzc0MCBcdWM3N2NcdWJkODAgXHVjOWQxXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHVjOWM4XHViM2M0IFx1Yzc3Y1x1YmQ4MCBcdWM5ZDFcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0LiBcdWIwYThcdWM3NDAgXHVjOWQxXHVjNzQwIFx1ZDMxMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FkXHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVhYzAwXHVjZTU4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWM5YzhcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YWM4YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjOWM0IFx1YzlkMVx1Yzc1OCBcdWFjMDBcdWNlNThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWQwNmNcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWQxIE5cdWNjNDRcdWM3NTggXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDMxNFx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjOWQxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5ZDFcdWM3NTggXHVjMjE4XHViMjk0IDI0XHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YzlkMVx1Yzc0NCBcdWFjZjVcdWQzYzlcdWQ1NThcdWFjOGMgXHViMDk4XHViMjA0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQzMTRcdWM1NDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzlkMVx1Yzc1OCBcdWFjMDBcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjNjA4XHVjODFjXHViMjk0IFx1YzdhZFx1YWNmYyBcdWM5YzhcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM5ZDEgNVx1Y2M0NFx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgNiwwMDAsMDAwLCAzMCwwMDAsMDAwLCAzLDAwMCwwMDAsIDExLDAwMCwwMDAsIDMsMDAwLDAwMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuIFx1YzdhZFx1Yzc3NCA2LDAwMCwwMDAgXHViMmVjXHViN2VjIFx1YzlkMSwgXHVjOWM4XHVjNzc0IDMsMDAwLDAwMCBcdWIyZWNcdWI3ZWMgXHVjOWQxIFx1YjQ1MCBcdWFjMWNcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzAwXHViYTc0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVhY2Y1XHVkM2M5XHVkNTU4XHVhYzhjIFx1YzlkMVx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMGE4XHViMjk0IFx1YzlkMSAoMTEsMDAwLDAwMCBcdWIyZWNcdWI3ZWMsIDMwLDAwMCwwMDAgXHViMmVjXHViN2VjKSBcdWM3NTggXHVkNTY5XHVjNzQwIDQxLDAwMCwwMDAgXHViMmVjXHViN2VjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MTYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2VsZWJyaXR5IFNwbGl0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Rpdm9yY2UuanBnXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjI2OXB4OyB3aWR0aDoyNjlweFwiIFwvPkphY2sgYW5kIEppbGwgaGF2ZSBkZWNpZGVkIHRvIHNlcGFyYXRlIGFuZCBkaXZpZGUgdGhlaXIgcHJvcGVydHkgZXF1YWxseS4gRWFjaCBvZiB0aGVpciBOIG1hbnNpb25zIGhhcyBhIHZhbHVlIGJldHdlZW4gMSwwMDAsMDAwIGFuZCA0MCwwMDAsMDAwIGRvbGxhcnMuIEphY2sgd2lsbCByZWNlaXZlIHNvbWUgb2YgdGhlIG1hbnNpb25zOyBKaWxsIHdpbGwgcmVjZWl2ZSBzb21lIG9mIHRoZSBtYW5zaW9uczsgdGhlIHJlbWFpbmluZyBtYW5zaW9ucyB3aWxsIGJlIHNvbGQsIGFuZCB0aGUgcHJvY2VlZHMgc3BsaXQgZXF1YWxseS48XC9wPlxyXG5cclxuPHA+TmVpdGhlciBKYWNrIG5vciBKaWxsIGNhbiB0b2xlcmF0ZSB0aGUgb3RoZXIgcmVjZWl2aW5nIHByb3BlcnR5IHdpdGggaGlnaGVyIHRvdGFsIHZhbHVlLiBUaGUgc3VtIG9mIHRoZSB2YWx1ZXMgb2YgdGhlIG1hbnNpb25zIEphY2sgcmVjZWl2ZXMgbXVzdCBiZSBlcXVhbCB0byB0aGUgc3VtIG9mIHRoZSB2YWx1ZXMgb2YgdGhlIG1hbnNpb25zIEppbGwgcmVjZWl2ZXMuIFNvIGxvbmcgYXMgdGhlIHZhbHVlIHRoYXQgZWFjaCByZWNlaXZlcyBpcyBlcXVhbCwgSmFjayBhbmQgSmlsbCB3b3VsZCBsaWtlIGVhY2ggdG8gcmVjZWl2ZSBwcm9wZXJ0eSBvZiB0aGUgaGlnaGVzdCBwb3NzaWJsZSB2YWx1ZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHZhbHVlcyBvZiBOIG1hbnNpb25zLCBjb21wdXRlIHRoZSB2YWx1ZSBvZiB0aGUgbWFuc2lvbnMgdGhhdCBtdXN0IGJlIHNvbGQgc28gdGhhdCB0aGUgcmVzdCBtYXkgYmUgZGl2aWRlZCBzbyBhcyB0byBzYXRpc2Z5IEphY2sgYW5kIEppbGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzZXF1ZW5jZSBvZiB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgbWFuc2lvbnMsIHdoaWNoIHdpbGwgYmUgbm8gbW9yZSB0aGFuIDI0LiBUaGlzIGxpbmUgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcywgZWFjaCBnaXZpbmcgdGhlIHZhbHVlIG9mIGEgbWFuc2lvbi4gVGhlIGZpbmFsIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgemVyby4gVGhpcyBsaW5lIGlzIG5vdCBhIHRlc3QgY2FzZSBhbmQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIsIHRoZSB2YWx1ZSBvZiB0aGUgbWFuc2lvbnMgdGhhdCBtdXN0IGJlIHNvbGQgc28gdGhhdCB0aGUgcmVzdCBtYXkgYmUgZGl2aWRlZCBzbyBhcyB0byBzYXRpc2Z5IEphY2sgYW5kIEppbGwuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5TdXBwb3NlIEphY2sgYW5kIEppbGwgb3duIDUgbWFuc2lvbnMgdmFsdWVkIGF0IDYsMDAwLDAwMCwgMzAsMDAwLDAwMCwgMywwMDAsMDAwLCAxMSwwMDAsMDAwLCBhbmQgMywwMDAsMDAwIGRvbGxhcnMuIFRvIHNhdGlzZnkgdGhlaXIgcmVxdWlyZW1lbnRzLCBKYWNrIG9yIEppbGwgd291bGQgcmVjZWl2ZSB0aGUgbWFuc2lvbiB3b3J0aCA2LDAwMCwwMDAgYW5kIHRoZSBvdGhlciB3b3VsZCByZWNlaXZlIGJvdGggbWFuc3Rpb25zIHdvcnRoIDMsMDAwLDAwMCBkb2xsYXJzLiBUaGUgbWFuc2lvbnMgd29ydGggMTEsMDAwLDAwMCBhbmQgMzAsMDAwLDAwMCBkb2xsYXJzIHdvdWxkIGJlIHNvbGQsIGZvciBhIHRvdGFsIG9mIDQxLDAwMCwwMDAgZG9sbGFycy4gVGhlIGFuc3dlciBpcyB0aGVyZWZvcmUgNDEwMDAwMDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=