시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
30 초 128 MB 25 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+XHVjN2FkXHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVhYzAwXHVjZTU4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWM5YzhcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YWM4YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjOWM0IFx1YzlkMVx1Yzc1OCBcdWFjMDBcdWNlNThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWQwNmNcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWQxIE5cdWNjNDRcdWM3NTggXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDMxNFx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjOWQxXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5ZDFcdWM3NTggXHVjMjE4XHViMjk0IDI0XHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YzlkMVx1Yzc0NCBcdWFjZjVcdWQzYzlcdWQ1NThcdWFjOGMgXHViMDk4XHViMjA0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQzMTRcdWM1NDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzlkMVx1Yzc1OCBcdWFjMDBcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjNjA4XHVjODFjXHViMjk0IFx1YzdhZFx1YWNmYyBcdWM5YzhcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM5ZDEgNVx1Y2M0NFx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgNiwwMDAsMDAwLCAzMCwwMDAsMDAwLCAzLDAwMCwwMDAsIDExLDAwMCwwMDAsIDMsMDAwLDAwMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuIFx1YzdhZFx1Yzc3NCA2LDAwMCwwMDAgXHViMmVjXHViN2VjIFx1YzlkMSwgXHVjOWM4XHVjNzc0IDMsMDAwLDAwMCBcdWIyZWNcdWI3ZWMgXHVjOWQxIFx1YjQ1MCBcdWFjMWNcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzAwXHViYTc0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVhY2Y1XHVkM2M5XHVkNTU4XHVhYzhjIFx1YzlkMVx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMGE4XHViMjk0IFx1YzlkMSAoMTEsMDAwLDAwMCBcdWIyZWNcdWI3ZWMsIDMwLDAwMCwwMDAgXHViMmVjXHViN2VjKSBcdWM3NTggXHVkNTY5XHVjNzQwIDQxLDAwMCwwMDAgXHViMmVjXHViN2VjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDE2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNlbGVicml0eSBTcGxpdCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kaXZvcmNlLmpwZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyNjlweDsgd2lkdGg6MjY5cHhcIiBcLz5KYWNrIGFuZCBKaWxsIGhhdmUgZGVjaWRlZCB0byBzZXBhcmF0ZSBhbmQgZGl2aWRlIHRoZWlyIHByb3BlcnR5IGVxdWFsbHkuIEVhY2ggb2YgdGhlaXIgTiBtYW5zaW9ucyBoYXMgYSB2YWx1ZSBiZXR3ZWVuIDEsMDAwLDAwMCBhbmQgNDAsMDAwLDAwMCBkb2xsYXJzLiBKYWNrIHdpbGwgcmVjZWl2ZSBzb21lIG9mIHRoZSBtYW5zaW9uczsgSmlsbCB3aWxsIHJlY2VpdmUgc29tZSBvZiB0aGUgbWFuc2lvbnM7IHRoZSByZW1haW5pbmcgbWFuc2lvbnMgd2lsbCBiZSBzb2xkLCBhbmQgdGhlIHByb2NlZWRzIHNwbGl0IGVxdWFsbHkuPFwvcD5cclxuXHJcbjxwPk5laXRoZXIgSmFjayBub3IgSmlsbCBjYW4gdG9sZXJhdGUgdGhlIG90aGVyIHJlY2VpdmluZyBwcm9wZXJ0eSB3aXRoIGhpZ2hlciB0b3RhbCB2YWx1ZS4gVGhlIHN1bSBvZiB0aGUgdmFsdWVzIG9mIHRoZSBtYW5zaW9ucyBKYWNrIHJlY2VpdmVzIG11c3QgYmUgZXF1YWwgdG8gdGhlIHN1bSBvZiB0aGUgdmFsdWVzIG9mIHRoZSBtYW5zaW9ucyBKaWxsIHJlY2VpdmVzLiBTbyBsb25nIGFzIHRoZSB2YWx1ZSB0aGF0IGVhY2ggcmVjZWl2ZXMgaXMgZXF1YWwsIEphY2sgYW5kIEppbGwgd291bGQgbGlrZSBlYWNoIHRvIHJlY2VpdmUgcHJvcGVydHkgb2YgdGhlIGhpZ2hlc3QgcG9zc2libGUgdmFsdWUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSB2YWx1ZXMgb2YgTiBtYW5zaW9ucywgY29tcHV0ZSB0aGUgdmFsdWUgb2YgdGhlIG1hbnNpb25zIHRoYXQgbXVzdCBiZSBzb2xkIHNvIHRoYXQgdGhlIHJlc3QgbWF5IGJlIGRpdmlkZWQgc28gYXMgdG8gc2F0aXNmeSBKYWNrIGFuZCBKaWxsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2VxdWVuY2Ugb2YgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOLCB0aGUgbnVtYmVyIG9mIG1hbnNpb25zLCB3aGljaCB3aWxsIGJlIG5vIG1vcmUgdGhhbiAyNC4gVGhpcyBsaW5lIGlzIGZvbGxvd2VkIGJ5IE4gbGluZXMsIGVhY2ggZ2l2aW5nIHRoZSB2YWx1ZSBvZiBhIG1hbnNpb24uIFRoZSBmaW5hbCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIHplcm8uIFRoaXMgbGluZSBpcyBub3QgYSB0ZXN0IGNhc2UgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgdmFsdWUgb2YgdGhlIG1hbnNpb25zIHRoYXQgbXVzdCBiZSBzb2xkIHNvIHRoYXQgdGhlIHJlc3QgbWF5IGJlIGRpdmlkZWQgc28gYXMgdG8gc2F0aXNmeSBKYWNrIGFuZCBKaWxsLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+U3VwcG9zZSBKYWNrIGFuZCBKaWxsIG93biA1IG1hbnNpb25zIHZhbHVlZCBhdCA2LDAwMCwwMDAsIDMwLDAwMCwwMDAsIDMsMDAwLDAwMCwgMTEsMDAwLDAwMCwgYW5kIDMsMDAwLDAwMCBkb2xsYXJzLiBUbyBzYXRpc2Z5IHRoZWlyIHJlcXVpcmVtZW50cywgSmFjayBvciBKaWxsIHdvdWxkIHJlY2VpdmUgdGhlIG1hbnNpb24gd29ydGggNiwwMDAsMDAwIGFuZCB0aGUgb3RoZXIgd291bGQgcmVjZWl2ZSBib3RoIG1hbnN0aW9ucyB3b3J0aCAzLDAwMCwwMDAgZG9sbGFycy4gVGhlIG1hbnNpb25zIHdvcnRoIDExLDAwMCwwMDAgYW5kIDMwLDAwMCwwMDAgZG9sbGFycyB3b3VsZCBiZSBzb2xkLCBmb3IgYSB0b3RhbCBvZiA0MSwwMDAsMDAwIGRvbGxhcnMuIFRoZSBhbnN3ZXIgaXMgdGhlcmVmb3JlIDQxMDAwMDAwLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==