시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 217 170 143 76.882%

문제

코딩 프로젝트 수업을 가르치는 수찬이는 프로젝트 팀을 가능하면 공정하게 구성하려고 한다. 프로젝트 팀 하나는 두 명의 학생으로 구성되는데, 각 학생들의 코딩 역량은 모두 다르다. 각 학생은 한 팀의 팀원이어야 한다. 공정성을 높이기 위해 수찬이는 팀원 코딩 역량의 합을 최대한 일정하게 유지하려고 한다. 학생들이 코딩 역량이 주어졌을 때 수찬이가 팀을 구성하는데 도움이 되는 프로그램을 작성하라.

문제를 간단하게 하기 위해, 학생 수는 2n이라 가정하자 (n은 양의 정수). 각 학생 si의 코딩 역량은 양의 정수 w(si)로 나타내면 한 i번째 팀 Gi의 코딩 역량은 w(Gi) = ∑sGiw(s)로 나타낼 수 있다. 작성할 프로그램 목적은 Sm = min{w(Gi) | 1 ≤ in}이 최대화되도록 n개의 팀 G1, G2, …, Gn 을 구성하고 이때 Sm을 출력하는 것이다.

예를 들어, 학생들의 코딩 역량이 {1, 7, 5, 8}로 주어졌다면 (8, 1), (7, 5)로 2개의 조를 짤 수 있으며 프로그램은 9를 출력해야 한다.

입력

입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 분리되어 주어진다 (1 ≤ w(si) ≤ 100,000). 학생들의 코딩 역량은 모두 다르다. 즉, ij이면 w(si) ≠ w(sj)이다.

출력

출력은 표준출력을 사용한다. 표준출력 한 행에 Sm을 출력한다.

예제 입력 1

2
1 7 5 8

예제 출력 1

9

예제 입력 2

3
1 7 3 5 9 2

예제 출력 2

8
W3sicHJvYmxlbV9pZCI6IjIwMDQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUHJvamVjdCBUZWFtcyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZjU0XHViNTI5IFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOCBcdWMyMThcdWM1YzVcdWM3NDQgXHVhYzAwXHViOTc0XHVjZTU4XHViMjk0IFx1YzIxOFx1Y2MyY1x1Yzc3NFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjggXHVkMzAwXHVjNzQ0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBcdWFjZjVcdWM4MTVcdWQ1NThcdWFjOGMgXHVhZDZjXHVjMTMxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTA0XHViODVjXHVjODFkXHVkMmI4IFx1ZDMwMCBcdWQ1NThcdWIwOThcdWIyOTQgXHViNDUwIFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHViMjk0XHViMzcwLCBcdWFjMDEgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWM1ZWRcdWI3YzlcdWM3NDAgXHViYWE4XHViNDUwIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVhYzAxIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWQ1NWMgXHVkMzAwXHVjNzU4IFx1ZDMwMFx1YzZkMFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNmNVx1YzgxNVx1YzEzMVx1Yzc0NCBcdWIxOTJcdWM3NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzIxOFx1Y2MyY1x1Yzc3NFx1YjI5NCBcdWQzMDBcdWM2ZDAgXHVjZjU0XHViNTI5IFx1YzVlZFx1YjdjOVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjIFx1Yzc3Y1x1YzgxNVx1ZDU1OFx1YWM4YyBcdWM3MjBcdWM5YzBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjZjU0XHViNTI5IFx1YzVlZFx1YjdjOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YzIxOFx1Y2MyY1x1Yzc3NFx1YWMwMCBcdWQzMDBcdWM3NDQgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0XHViMzcwIFx1YjNjNFx1YzZjMFx1Yzc3NCBcdWI0MThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViOTdjIFx1YWMwNFx1YjJlOFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWQ1NTlcdWMwZGQgXHVjMjE4XHViMjk0IDI8ZW0+bjxcL2VtPlx1Yzc3NFx1Yjc3YyBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAgKDxlbT5uPFwvZW0+XHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTgpLiBcdWFjMDEgXHVkNTU5XHVjMGRkIDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPlx1Yzc1OCBcdWNmNTRcdWI1MjkgXHVjNWVkXHViN2M5XHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggPGVtPnc8XC9lbT4oPGVtPnM8c3ViPmk8XC9zdWI+PFwvZW0+KVx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzQgXHVkNTVjIDxlbT5pPFwvZW0+XHViYzg4XHVjOWY4IFx1ZDMwMCA8ZW0+RzxzdWI+aTxcL3N1Yj48XC9lbT5cdWM3NTggXHVjZjU0XHViNTI5IFx1YzVlZFx1YjdjOVx1Yzc0MCA8ZW0+dzxcL2VtPig8ZW0+RzxzdWI+aTxcL3N1Yj48XC9lbT4pID0gJnN1bTs8c3ViPjxlbT5zPFwvZW0+JmlzaW47PGVtPkc8c3ViPmk8XC9zdWI+PFwvZW0+PFwvc3ViPjxlbT53PFwvZW0+KDxlbT5zPFwvZW0+KVx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzkxXHVjMTMxXHVkNTYwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWJhYTlcdWM4MDFcdWM3NDAgPGVtPlM8c3ViPm08XC9zdWI+PFwvZW0+Jm5ic3A7PSBtaW57PGVtPnc8XC9lbT4oPGVtPkc8c3ViPmk8XC9zdWI+PFwvZW0+KSB8IDEgJmxlOyA8ZW0+aTxcL2VtPiAmbGU7IDxlbT5uPFwvZW0+fVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ2NTRcdWI0MThcdWIzYzRcdWI4NWQgPGVtPm48XC9lbT5cdWFjMWNcdWM3NTggXHVkMzAwIDxlbT5HPFwvZW0+PHN1Yj4xPFwvc3ViPiwgPGVtPkc8XC9lbT48c3ViPjI8XC9zdWI+LCAmaGVsbGlwOywmbmJzcDs8ZW0+RzxzdWI+bjxcL3N1Yj48XC9lbT4gXHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YWNlMCBcdWM3NzRcdWI1NGMgPGVtPlM8c3ViPm08XC9zdWI+PFwvZW0+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWNmNTRcdWI1MjkgXHVjNWVkXHViN2M5XHVjNzc0IHsxLCA3LCA1LCA4fVx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWIyZTRcdWJhNzQgKDgsIDEpLCAoNywgNSlcdWI4NWMgMlx1YWMxY1x1Yzc1OCBcdWM4NzBcdWI5N2MgXHVjOWU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIDlcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1ODlcdWM1ZDBcdWIyOTQgXHVkMzAwIFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCA8ZW0+bjxcL2VtPigxICZsZTsgPGVtPm48XC9lbT4gJmxlOyA1LDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1ZDU4OVx1YzVkMCBcdWQ1NTlcdWMwZGQgPGVtPnM8c3ViPmk8XC9zdWI+PFwvZW0+IFx1Yzc1OCBcdWNmNTRcdWI1MjkgXHVjNWVkXHViN2M5IDxlbT53PFwvZW0+KDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPilcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IDI8ZW0+bjxcL2VtPlx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgPGVtPnc8XC9lbT4oPGVtPnM8c3ViPmk8XC9zdWI+PFwvZW0+KSAmbGU7IDEwMCwwMDApLiBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZjU0XHViNTI5IFx1YzVlZFx1YjdjOVx1Yzc0MCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViMmU0LiBcdWM5ODksIDxlbT5pPFwvZW0+ICZuZTsgPGVtPmo8XC9lbT5cdWM3NzRcdWJhNzQgPGVtPnc8XC9lbT4oPGVtPnM8c3ViPmk8XC9zdWI+PFwvZW0+KSAmbmU7IDxlbT53PFwvZW0+KDxlbT5zPHN1Yj5qPFwvc3ViPjxcL2VtPilcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNSBcdWQ1NWMgXHVkNTg5XHVjNWQwIDxlbT5TPHN1Yj5tPFwvc3ViPjxcL2VtPlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAwNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcm9qZWN0IFRlYW1zIiwiZGVzY3JpcHRpb24iOiI8cD5TdWNoYW4gaXMgdGVhY2hpbmcgYSBjb2RpbmcgcHJvamVjdCBjbGFzcyBhbmQgd2FudHMgdG8gbWFrZSBwcm9qZWN0IHRlYW1zIGFzIGZhaXIgYXMgcG9zc2libGUuIEEgcHJvamVjdCB0ZWFtIGNvbnNpc3RzIG9mIHR3byBzdHVkZW50cywgYnV0IHRoZSBjb2RpbmcgYWJpbGl0aWVzIG9mIHN0dWRlbnRzIGFyZSBhbGwgZGlmZmVyZW50LiBFdmVyeSBzdHVkZW50IHNob3VsZCBiZSBhIG1lbWJlciBvZiBhIHNpbmdsZSB0ZWFtLiBUbyBwcm9tb3RlIGZhaXJuZXNzLCBoZSB3YW50cyB0byBtYWtlIHByb2plY3QgdGVhbXMgd2hlcmUgdGhlIHN1bSBvZiB0aGUgY29kaW5nIGFiaWxpdHkgb2YgdGVhbSBtZW1iZXJzIGlzIGFzIGV2ZW4gYXMgcG9zc2libGUuIFdyaXRlIGEgcHJvZ3JhbSB0byBoZWxwIFN1Y2hhbiB0byBtYWtlIHByb2plY3QgdGVhbXMgZ2l2ZW4gdGhlIGNvZGluZyBhYmlsaXRpZXMgb2Ygc3R1ZGVudHMuPFwvcD5cclxuXHJcbjxwPlRvIG1ha2UgdGhlIHByb2JsZW0gc2ltcGxlLCB0aGUgbnVtYmVyIG9mIHN0dWRlbnRzIGlzIGV2ZW4sIHNheSAyPGVtPm48XC9lbT4sIHdoZXJlIDxlbT5uPFwvZW0+IGlzIGEgcG9zaXRpdmUgaW50ZWdlci4gVGhlIGNvZGluZyBhYmlsaXR5IG9mIGEgc3R1ZGVudCA8ZW0+czxzdWI+aTxcL3N1Yj48XC9lbT4gaXMgcmVwcmVzZW50ZWQgYnkgYSBwb3NpdGl2ZSBpbnRlZ2VyIDxlbT53PFwvZW0+KDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPikuIFRoZSBnb2FsIG9mIHlvdXIgcHJvZ3JhbSBpcyB0byBtYWtlIDxlbT5uPFwvZW0+IHRlYW1zLCA8ZW0+RzxcL2VtPjxzdWI+MTxcL3N1Yj4sIDxlbT5HPFwvZW0+PHN1Yj4yPFwvc3ViPiwgJmhlbGxpcDsgLCBhbmQgPGVtPkc8c3ViPm48XC9zdWI+PFwvZW0+LCB0byBtYXhpbWl6ZSA8ZW0+UzxzdWI+bTxcL3N1Yj48XC9lbT4mbmJzcDs9IG1pbns8ZW0+dzxcL2VtPig8ZW0+RzxzdWI+aTxcL3N1Yj48XC9lbT4pIHwgMSAmbGU7IDxlbT5pPFwvZW0+ICZsZTsgPGVtPm48XC9lbT59IGFuZCBwcmludCA8ZW0+UzxzdWI+bTxcL3N1Yj48XC9lbT4uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgY29kaW5nIGFiaWxpdGllcyBvZiB0aGUgc3R1ZGVudHMgYXJlIGdpdmVuIGJ5IHsxLCA3LCA1LCA4fSwgeW91IGNhbiBtYWtlIHR3byB0ZWFtcywgZWFjaCB3aXRoICg4LCAxKSBhbmQgKDcsIDUpLCBhbmQgeW91ciBwcm9ncmFtIHNob3VsZCBwcmludCA5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlciA8ZW0+bjxcL2VtPiAoMSAmbGU7IDxlbT5uPFwvZW0+ICZsZTsgNSwwMDApLCB3aGVyZSA8ZW0+bjxcL2VtPiBpcyB0aGUgbnVtYmVyIG9mIHRlYW1zIHRvIG1ha2UuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgMjxlbT5uPFwvZW0+IHBvc2l0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNwYWNlLCBlYWNoIG9mIHdoaWNoIHJlcHJlc2VudHMgdGhlIGNvZGluZyBhYmlsaXR5IDxlbT53PFwvZW0+KDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPikgb2YgYSBzdHVkZW50IDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPiAoMSAmbGU7IDxlbT53PFwvZW0+KDxlbT5zPHN1Yj5pPFwvc3ViPjxcL2VtPikgJmxlOyAxMDAsMDAwKS4gTm90ZSB0aGF0IHRoZSBjb2RpbmcgYWJpbGl0aWVzIG9mIHN0dWRlbnRzIGFyZSBhbGwgZGlmZmVyZW50LCB0aGF0IGlzLCA8ZW0+dzxcL2VtPig8ZW0+czxzdWI+aTxcL3N1Yj48XC9lbT4pICZuZTsgPGVtPnc8XC9lbT4oPGVtPnM8c3ViPmo8XC9zdWI+PFwvZW0+KSBpZiA8ZW0+aTxcL2VtPiAmbmU7IDxlbT5qPFwvZW0+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgY29udGFpbmluZyA8ZW0+UzxzdWI+bTxcL3N1Yj48XC9lbT4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d