시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
30 초 128 MB 22 5 5 55.556%

문제

잭과 질은 이혼을 하게 되었고, 두 사람은 재산을 공평하게 나누려고 한다. 두 사람은 집을 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+XHVjN2FkXHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVhYzAwXHVjZTU4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWM5YzhcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YWM4YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVhYzAxIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMDBcdWM5YzQgXHVjOWQxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhYzAwXHVjN2E1IFx1ZDA2Y1x1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5ZDEgTlx1Y2M0NFx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMzE0XHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVhYzAwXHVjZTU4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzlkMVx1Yzc1OCBcdWMyMThcdWIyOTQgMjRcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjOWQxXHVjNzQ0IFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YWM4YyBcdWIwOThcdWIyMDRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDMxNFx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjOWQxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjN2FkXHVhY2ZjIFx1YzljOFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzlkMSA1XHVjYzQ0XHVjNzU4IFx1YWMwMFx1Y2U1OFx1YWMwMCA2LDAwMCwwMDAsIDMwLDAwMCwwMDAsIDMsMDAwLDAwMCwgMTEsMDAwLDAwMCwgMywwMDAsMDAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC4gXHVjN2FkXHVjNzc0IDYsMDAwLDAwMCBcdWIyZWNcdWI3ZWMgXHVjOWQxLCBcdWM5YzhcdWM3NzQgMywwMDAsMDAwIFx1YjJlY1x1YjdlYyBcdWM5ZDEgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWFjZjVcdWQzYzlcdWQ1NThcdWFjOGMgXHVjOWQxXHVjNzQ0IFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIwYThcdWIyOTQgXHVjOWQxICgxMSwwMDAsMDAwIFx1YjJlY1x1YjdlYywgMzAsMDAwLDAwMCBcdWIyZWNcdWI3ZWMpIFx1Yzc1OCBcdWQ1NjlcdWM3NDAgNDEsMDAwLDAwMCBcdWIyZWNcdWI3ZWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MTYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2VsZWJyaXR5IFNwbGl0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Rpdm9yY2UuanBnXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjI2OXB4OyB3aWR0aDoyNjlweFwiIFwvPkphY2sgYW5kIEppbGwgaGF2ZSBkZWNpZGVkIHRvIHNlcGFyYXRlIGFuZCBkaXZpZGUgdGhlaXIgcHJvcGVydHkgZXF1YWxseS4gRWFjaCBvZiB0aGVpciBOIG1hbnNpb25zIGhhcyBhIHZhbHVlIGJldHdlZW4gMSwwMDAsMDAwIGFuZCA0MCwwMDAsMDAwIGRvbGxhcnMuIEphY2sgd2lsbCByZWNlaXZlIHNvbWUgb2YgdGhlIG1hbnNpb25zOyBKaWxsIHdpbGwgcmVjZWl2ZSBzb21lIG9mIHRoZSBtYW5zaW9uczsgdGhlIHJlbWFpbmluZyBtYW5zaW9ucyB3aWxsIGJlIHNvbGQsIGFuZCB0aGUgcHJvY2VlZHMgc3BsaXQgZXF1YWxseS48XC9wPlxyXG5cclxuPHA+TmVpdGhlciBKYWNrIG5vciBKaWxsIGNhbiB0b2xlcmF0ZSB0aGUgb3RoZXIgcmVjZWl2aW5nIHByb3BlcnR5IHdpdGggaGlnaGVyIHRvdGFsIHZhbHVlLiBUaGUgc3VtIG9mIHRoZSB2YWx1ZXMgb2YgdGhlIG1hbnNpb25zIEphY2sgcmVjZWl2ZXMgbXVzdCBiZSBlcXVhbCB0byB0aGUgc3VtIG9mIHRoZSB2YWx1ZXMgb2YgdGhlIG1hbnNpb25zIEppbGwgcmVjZWl2ZXMuIFNvIGxvbmcgYXMgdGhlIHZhbHVlIHRoYXQgZWFjaCByZWNlaXZlcyBpcyBlcXVhbCwgSmFjayBhbmQgSmlsbCB3b3VsZCBsaWtlIGVhY2ggdG8gcmVjZWl2ZSBwcm9wZXJ0eSBvZiB0aGUgaGlnaGVzdCBwb3NzaWJsZSB2YWx1ZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHZhbHVlcyBvZiBOIG1hbnNpb25zLCBjb21wdXRlIHRoZSB2YWx1ZSBvZiB0aGUgbWFuc2lvbnMgdGhhdCBtdXN0IGJlIHNvbGQgc28gdGhhdCB0aGUgcmVzdCBtYXkgYmUgZGl2aWRlZCBzbyBhcyB0byBzYXRpc2Z5IEphY2sgYW5kIEppbGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzZXF1ZW5jZSBvZiB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgbWFuc2lvbnMsIHdoaWNoIHdpbGwgYmUgbm8gbW9yZSB0aGFuIDI0LiBUaGlzIGxpbmUgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcywgZWFjaCBnaXZpbmcgdGhlIHZhbHVlIG9mIGEgbWFuc2lvbi4gVGhlIGZpbmFsIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgemVyby4gVGhpcyBsaW5lIGlzIG5vdCBhIHRlc3QgY2FzZSBhbmQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIsIHRoZSB2YWx1ZSBvZiB0aGUgbWFuc2lvbnMgdGhhdCBtdXN0IGJlIHNvbGQgc28gdGhhdCB0aGUgcmVzdCBtYXkgYmUgZGl2aWRlZCBzbyBhcyB0byBzYXRpc2Z5IEphY2sgYW5kIEppbGwuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5TdXBwb3NlIEphY2sgYW5kIEppbGwgb3duIDUgbWFuc2lvbnMgdmFsdWVkIGF0IDYsMDAwLDAwMCwgMzAsMDAwLDAwMCwgMywwMDAsMDAwLCAxMSwwMDAsMDAwLCBhbmQgMywwMDAsMDAwIGRvbGxhcnMuIFRvIHNhdGlzZnkgdGhlaXIgcmVxdWlyZW1lbnRzLCBKYWNrIG9yIEppbGwgd291bGQgcmVjZWl2ZSB0aGUgbWFuc2lvbiB3b3J0aCA2LDAwMCwwMDAgYW5kIHRoZSBvdGhlciB3b3VsZCByZWNlaXZlIGJvdGggbWFuc3Rpb25zIHdvcnRoIDMsMDAwLDAwMCBkb2xsYXJzLiBUaGUgbWFuc2lvbnMgd29ydGggMTEsMDAwLDAwMCBhbmQgMzAsMDAwLDAwMCBkb2xsYXJzIHdvdWxkIGJlIHNvbGQsIGZvciBhIHRvdGFsIG9mIDQxLDAwMCwwMDAgZG9sbGFycy4gVGhlIGFuc3dlciBpcyB0aGVyZWZvcmUgNDEwMDAwMDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d