시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 79 29 16 36.364%

문제

음 아닌 정수들로 이루어진 두 개의 집합 S와 T가 있다. S의 원소들과 T의 원소들을 짝지으려고 하는데, 다음과 같은 규칙을 만족하도록 하고 싶다.

1) S의 임의의 원소 s는 T의 어떤 원소와도 짝지어질 수 있다. 또한 T의 임의의 원소 t도 S의 어떤 원소와도 짝지어질 수 있다.

2) S의 모든 원소는 적어도 하나의 T의 원소와는 짝지어져야 하고, T의 모든 원소 역시 적어도 하나의 S의 원소와는 짝지어져야 한다.

예를 들어 S={2, 8, 9, 10, 11}, T={0, 3, 4, 6, 7, 11}을 보자. {(2, 0), (2, 3), (2, 4), (8, 6), (9, 7), (10, 11), (11, 11)}은 규칙을 만족하는 경우가 된다. 하지만 {(2, 0), (8, 3), (9, 4), (10, 6), (11, 7)}은 규칙을 만족하는 경우가 아닌데, T의 원소 11이 S의 어떤 원소와도 짝지어지지 않았기 때문이다.

각각의 짝 (a, b)의 비용이란, a와 b의 차이의 절대값으로 정의된다. 우리는 모든 비용의 합을 최소로 하도록 S의 원소들과 T의 원소들을 짝지으려 한다. 위에서 주어진 S와 T에 대해서는 10이 최소의 비용합이 된다.

S와 T가 주어지면, 모든 비용의 합을 최소로 하도록 S의 원소들과 T의 원소들을 짝지어 주는 프로그램을 작성하시오.

입력

첫째 줄에 S의 원소의 개수와 T의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 S의 원소, 셋째 줄에는 T의 원소가 첫째 줄에 주어진 개수만큼 빈 칸을 사이에 두고 증가하는 순서대로 주어진다. 각 집합의 원소의 크기는 500,000 이하이며, 주어지는 수는 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 최소의 비용합을 출력한다.

예제 입력 1

5 6
2 8 9 10 11
0 3 4 6 7 11

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjE2NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc0YyBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzlkMVx1ZDU2OSBTXHVjNjQwIFRcdWFjMDAgXHVjNzg4XHViMmU0LiBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1YWNmYyBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM5ZGRcdWM5YzBcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC48XC9wPlxyXG48cD4xKSBTXHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM2ZDBcdWMxOGMgc1x1YjI5NCBUXHVjNzU4IFx1YzViNFx1YjVhNCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIzYzQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMFx1ZDU1YyBUXHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM2ZDBcdWMxOGMgdFx1YjNjNCBTXHVjNzU4IFx1YzViNFx1YjVhNCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIzYzQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+MikgU1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggVFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIyOTQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjODM4XHVjNTdjIFx1ZDU1OFx1YWNlMCwgVFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjIFx1YzVlZFx1YzJkYyBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHVjNzU4IFNcdWM3NTggXHVjNmQwXHVjMThjXHVjNjQwXHViMjk0IFx1YzlkZFx1YzljMFx1YzViNFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBTPXsyLCA4LCA5LCAxMCwgMTF9LCBUPXswLCAzLCA0LCA2LCA3LCAxMX1cdWM3NDQgXHViY2Y0XHVjNzkwLiB7KDIsIDApLCAoMiwgMyksICgyLCA0KSwgKDgsIDYpLCAoOSwgNyksICgxMCwgMTEpLCAoMTEsIDExKX1cdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgeygyLCAwKSwgKDgsIDMpLCAoOSwgNCksICgxMCwgNiksICgxMSwgNyl9XHVjNzQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJjY1x1YjM3MCwgVFx1Yzc1OCBcdWM2ZDBcdWMxOGMgMTFcdWM3NzQgU1x1Yzc1OCBcdWM1YjRcdWI1YTQgXHVjNmQwXHVjMThjXHVjNjQwXHViM2M0IFx1YzlkZFx1YzljMFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5ZGQgKGEsIGIpXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NFx1Yjc4MCwgYVx1YzY0MCBiXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjNjNFx1Yjg1ZCBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1YWNmYyBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM5ZGRcdWM5YzBcdWM3M2NcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFNcdWM2NDAgVFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgMTBcdWM3NzQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YmU0NFx1YzZhOVx1ZDU2OVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+U1x1YzY0MCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHViYWE4XHViNGUwIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjNjNFx1Yjg1ZCBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1YWNmYyBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM5ZGRcdWM5YzBcdWM1YjQgXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgU1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFRcdWM3NTggXHVjNmQwXHVjMThjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFNcdWM3NTggXHVjNmQwXHVjMThjLCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFRcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWMxY1x1YzIxOFx1YjljY1x1ZDA3YyBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVjNmQwXHVjMThjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCA1MDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YmE3MCwgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxOFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSAxLDAwMCwwMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTY1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik51bWJlciIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIGdpdmVuIHR3byBzZXRzIFMgYW5kIFQgb2YgbnVtYmVycywgbGV0IGEgbWF0Y2hpbmcgb2YgUyBhbmQgVCBiZSBhIHNldCBvZiBwYWlycyAocywgdCksIHMmaXNpbjtTLCB0JmlzaW47VCBzdWNoIHRoYXQgZWFjaCBudW1iZXIgaW4gUyBpcyBwYWlyZWQgd2l0aCBhdCBsZWFzdCBvbmUgbnVtYmVyIGluIFQgYW5kIGVhY2ggbnVtYmVyIGluIFQgaXMgcGFpcmVkIHdpdGggYXQgbGVhc3Qgb25lIG51bWJlciBpbiBTLiBGb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyBpcyBhIG1hdGNoaW5nIG9mIHR3byBzZXRzIFM9ezIsIDgsIDksIDEwLCAxMX0sIFQ9ezAsIDMsIDQsIDYsIDcsIDExfTombmJzcDs8XC9wPlxyXG5cclxuPHA+TTEgPXsoMiwgMCksICgyLCAzKSwgKDIsIDQpLCAoOCwgNiksICg5LCA3KSwgKDEwLCAxMSksICgxMSwgMTEpfTxcL3A+XHJcblxyXG48cD5XaGVyZWFzIHRoZSBmb2xsb3dpbmcgaXMgbm90IGEgbWF0Y2hpbmcgb2YgUyBhbmQgVCwmbmJzcDs8XC9wPlxyXG5cclxuPHA+TTIgPXsoMiwgMCksICg4LCAzKSwgKDksIDQpLCAoMTAsIDYpLCAoMTEsIDcpfSZuYnNwOzxcL3A+XHJcblxyXG48cD5zaW5jZSB0aGUgbnVtYmVyIDExIGluIHNldCBUIGlzIG5vdCBwYWlyZWQgd2l0aCBhbnkgbnVtYmVyIGluIFMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBhIHBhaXIgKGEsIGIpIGluIGEgbWF0Y2hpbmcsIHRoZSBjb3N0IG9mIHRoZSBwYWlyIGlzIGRlZmluZWQgdG8gYmUgdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gYSBhbmQgYi4gVGhlIGNvc3Qgb2YgYSBtYXRjaGluZyBpcyB0aGUgc3VtIG9mIHRoZSBjb3N0IG9mIGFsbCBwYWlycyBpbiB0aGUgbWF0Y2hpbmcuIEZvciBleGFtcGxlLCB0aGUgY29zdCBvZiB0aGUgbWF0Y2hpbmcgTTEgaXMgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHR3byBzZXRzIG9mIG51bWJlcnMsIGNvbXB1dGUgdGhlIG1pbmltdW0gY29zdCBtYXRjaGluZyBvZiB0aGUgdHdvIHNldHMuIEZvciBleGFtcGxlLCB0aGUgbWF0Y2hpbmcgTTEgaXMgYSBtaW5pbXVtIGNvc3QgbWF0Y2hpbmcgb2YgdGhlIGdpdmVuIHR3byBzZXRzIFMgYW5kIFQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0d28gaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyLCBuMSAsIGlzIHRoZSBudW1iZXIgb2YgaW50ZWdlcnMgaW4gdGhlIGZpcnN0IHNldCwgYW5kIHRoZSBzZWNvbmQgaW50ZWdlciwgbjIgLCBpcyB0aGUgbnVtYmVyIG9mIGludGVnZXJzIGluIHRoZSBzZWNvbmQgc2V0LCB3aGVyZSAxICZsZTsgbjEsIG4yICZsZTsgNTAsMDAwLiBUaGUgc2Vjb25kIGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgbjEgaW50ZWdlcnMgZm9yIHRoZSBmaXJzdCBzZXQgYW5kIHRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG4yIGludGVnZXJzIGZvciB0aGUgc2Vjb25kIHNldC4gVGhlIGludGVnZXJzIGluIGVhY2ggc2V0IGFyZSBhcnJhbmdlZCBpbiBpbmNyZWFzaW5nIG9yZGVyLiBBbGwgaW5wdXQgaW50ZWdlcnMgYXJlIGJldHdlZW4gMCBhbmQgMTAwLDAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIGNvc3Qgb2YgdGhlIG1pbmltdW0gY29zdCBtYXRjaGluZyBvZiB0aGUgdHdvIHNldHMgb2YgaW50ZWdlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgc2hvd3Mgc2FtcGxlIGlucHV0IGFuZCBvdXRwdXQgZm9yIHR3byB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2007 J번

  • 문제를 번역한 사람: author5