시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 49 7 7 25.000%

문제

대한 레슬링 협회는 다가오는 올림픽 선발전을 대비하기 위해 소속 선수들을 두 팀으로 나누려고 한다.

모든 선수는 두 팀 중 하나에 소속되어야 한다. 또, 두 팀에 소속된 선수의 차이는 1을 넘어갈 수 없다. 마지막으로, 각 팀의 몸무게의 합의 차이는 최소가 되어야 한다.

모든 선수들의 몸무게가 주어졌을 때, 위의 조건을 지키면서 팀을 나눈 다음, 각 팀의 몸무게의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선수의 수 n이 주어진다. 다음 n개 줄에는 각 선수의 몸무게가 주어진다. 모뭄게는 1보다 크거나 같고, 450보다 작거나 같은 정수이다. 협회에 소속된 선수의 수는 100명을 넘지 않는다.

출력

각 팀의 몸무게의 합을 공백으로 구분해 출력한다. 합이 작은 것을 먼저 출력한다. 

예제 입력 1

3
100
90
200

예제 출력 1

190 200
W3sicHJvYmxlbV9pZCI6Ijk0MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWMyYWNcdWI5YzEgXHVkMzAwIFx1YzEyMFx1YmMxYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViMzAwXHVkNTVjIFx1YjgwOFx1YzJhY1x1YjljMSBcdWQ2MTFcdWQ2OGNcdWIyOTQgXHViMmU0XHVhYzAwXHVjNjI0XHViMjk0IFx1YzYyY1x1YjliY1x1ZDUzZCBcdWMxMjBcdWJjMWNcdWM4MDRcdWM3NDQgXHViMzAwXHViZTQ0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxOGNcdWMxOGQgXHVjMTIwXHVjMjE4XHViNGU0XHVjNzQ0IFx1YjQ1MCBcdWQzMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzEyMFx1YzIxOFx1YjI5NCBcdWI0NTAgXHVkMzAwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM1ZDAgXHVjMThjXHVjMThkXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVkMzAwXHVjNWQwIFx1YzE4Y1x1YzE4ZFx1YjQxYyBcdWMxMjBcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IDFcdWM3NDQgXHViMTE4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVhYzAxIFx1ZDMwMFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzEyMFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVkMzAwXHVjNzQ0IFx1YjA5OFx1YjIwOCBcdWIyZTRcdWM3NGMsIFx1YWMwMSBcdWQzMDBcdWM3NTggXHViYWI4XHViYjM0XHVhYzhjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMxMjBcdWMyMThcdWM3NTggXHViYWI4XHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViYjQ0XHVhYzhjXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgNDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWQ2MTFcdWQ2OGNcdWM1ZDAgXHVjMThjXHVjMThkXHViNDFjIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMyMThcdWIyOTQgMTAwXHViYTg1XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDMwMFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NjlcdWM3NzQgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWJhM2NcdWM4MDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXcmVzdGxpbmcgVGVhbXMgU2VsZWN0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgVGhhaSBXcmVzdGxpbmcgQXNzb2NpYXRpb24gbXVzdCBkaXZpZGUgaXRzIG1lbWJlcnMgaW50byB0d28gdGVhbXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggcGVyc29uIG11c3QgYmUgb24gb25lIHRlYW0gb3IgdGhlIG90aGVyOyB0aGUgbnVtYmVyIG9mIHBlb3BsZSBvbiB0aGUgdHdvIHRlYW1zIG11c3Qgbm90IGRpZmZlciBieSBtb3JlIHRoYW4gMTsgdGhlIHRvdGFsIHdlaWdodCBvZiB0aGUgcGVvcGxlIG9uIGVhY2ggdGVhbSBzaG91bGQgYmUgYXMgbmVhcmx5IGVxdWFsIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgbiB0aGUgbnVtYmVyIG9mIHBlb3BsZSBpbiB0aGUgYXNzb2NpYXRpb24sIGFuZCBuIGxpbmVzIGZvbGxvdy4gVGhlIGZpcnN0IGxpbmUgZ2l2ZXMgdGhlIHdlaWdodCBvZiBwZXJzb24gMTsgdGhlIHNlY29uZCB0aGUgd2VpZ2h0IG9mIHBlcnNvbiAyOyBhbmQgc28gb24uIEVhY2ggd2VpZ2h0IGlzIGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCA0NTAuIFRoZXJlIGFyZSBhdCBtb3N0IDEwMCBwZW9wbGUgaW4gdGhlIGFzc29jaWF0aW9uLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgb3V0cHV0IHdpbGwgYmUgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIDIgbnVtYmVyczogdGhlIHRvdGFsIHdlaWdodCBvZiB0aGUgcGVvcGxlIG9uIG9uZSB0ZWFtLCBhbmQgdGhlIHRvdGFsIHdlaWdodCBvZiB0aGUgcGVvcGxlIG9uIHRoZSBvdGhlciB0ZWFtLiBJZiB0aGVzZSBudW1iZXJzIGRpZmZlciwgZ2l2ZSB0aGUgc21hbGxlciBmaXJzdC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=