시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 133 51 38 41.758%

문제

음 아닌 정수들로 이루어진 두 개의 집합 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
W3sicHJvYmxlbV9pZCI6IjE2NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMTggKEhhcmQpIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NGMgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1YjRlNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM5ZDFcdWQ1NjkgU1x1YzY0MCBUXHVhYzAwIFx1Yzc4OFx1YjJlNC4gU1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWFjZmMgVFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NDQgXHVjOWRkXHVjOWMwXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+U1x1Yzc1OCBcdWM3ODRcdWM3NThcdWM3NTggXHVjNmQwXHVjMThjIHNcdWIyOTQgVFx1Yzc1OCBcdWM1YjRcdWI1YTQgXHVjNmQwXHVjMThjXHVjNjQwXHViM2M0IFx1YzlkZFx1YzljMFx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMgVFx1Yzc1OCBcdWM3ODRcdWM3NThcdWM3NTggXHVjNmQwXHVjMThjIHRcdWIzYzQgU1x1Yzc1OCBcdWM1YjRcdWI1YTQgXHVjNmQwXHVjMThjXHVjNjQwXHViM2M0IFx1YzlkZFx1YzljMFx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5TXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGNcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YzY0MFx1YjI5NCBcdWM5ZGRcdWM5YzBcdWM1YjRcdWM4MzhcdWM1N2MgXHVkNTU4XHVhY2UwLCBUXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGMgXHVjNWVkXHVjMmRjIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggU1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIyOTQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFM9ezIsIDgsIDksIDEwLCAxMX0sIFQ9ezAsIDMsIDQsIDYsIDcsIDExfVx1Yzc0NCBcdWJjZjRcdWM3OTAuIHsoMiwgMCksICgyLCAzKSwgKDIsIDQpLCAoOCwgNiksICg5LCA3KSwgKDEwLCAxMSksICgxMSwgMTEpfVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyB7KDIsIDApLCAoOCwgMyksICg5LCA0KSwgKDEwLCA2KSwgKDExLCA3KX1cdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNTQ0XHViMmNjXHViMzcwLCBUXHVjNzU4IFx1YzZkMFx1YzE4YyAxMVx1Yzc3NCBTXHVjNzU4IFx1YzViNFx1YjVhNCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIzYzQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YzU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5ZGQgKGEsIGIpXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NFx1Yjc4MCwgYVx1YzY0MCBiXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjNjNFx1Yjg1ZCBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1YWNmYyBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM5ZGRcdWM5YzBcdWM3M2NcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFNcdWM2NDAgVFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgMTBcdWM3NzQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YmU0NFx1YzZhOVx1ZDU2OVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlNcdWM2NDAgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWJlNDRcdWM2YTlcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWIzYzRcdWI4NWQgU1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWFjZmMgVFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NDQgXHVjOWRkXHVjOWMwXHVjNWI0IFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgVFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgU1x1Yzc1OCBcdWM2ZDBcdWMxOGMsIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgVFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzFjXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDUwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxOFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSAxLDAwMCwwMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGNcdWM3NTggXHViZTQ0XHVjNmE5XHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNjU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTnVtYmVyIChIYXJkKSIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIGdpdmVuIHR3byBzZXRzIFMgYW5kIFQgb2YgbnVtYmVycywgbGV0IGEgbWF0Y2hpbmcgb2YgUyBhbmQgVCBiZSBhIHNldCBvZiBwYWlycyAocywgdCksIHMmaXNpbjtTLCB0JmlzaW47VCBzdWNoIHRoYXQgZWFjaCBudW1iZXIgaW4gUyBpcyBwYWlyZWQgd2l0aCBhdCBsZWFzdCBvbmUgbnVtYmVyIGluIFQgYW5kIGVhY2ggbnVtYmVyIGluIFQgaXMgcGFpcmVkIHdpdGggYXQgbGVhc3Qgb25lIG51bWJlciBpbiBTLiBGb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyBpcyBhIG1hdGNoaW5nIG9mIHR3byBzZXRzIFM9ezIsIDgsIDksIDEwLCAxMX0sIFQ9ezAsIDMsIDQsIDYsIDcsIDExfTombmJzcDs8XC9wPlxyXG5cclxuPHA+TTEgPXsoMiwgMCksICgyLCAzKSwgKDIsIDQpLCAoOCwgNiksICg5LCA3KSwgKDEwLCAxMSksICgxMSwgMTEpfTxcL3A+XHJcblxyXG48cD5XaGVyZWFzIHRoZSBmb2xsb3dpbmcgaXMgbm90IGEgbWF0Y2hpbmcgb2YgUyBhbmQgVCwmbmJzcDs8XC9wPlxyXG5cclxuPHA+TTIgPXsoMiwgMCksICg4LCAzKSwgKDksIDQpLCAoMTAsIDYpLCAoMTEsIDcpfSZuYnNwOzxcL3A+XHJcblxyXG48cD5zaW5jZSB0aGUgbnVtYmVyIDExIGluIHNldCBUIGlzIG5vdCBwYWlyZWQgd2l0aCBhbnkgbnVtYmVyIGluIFMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBhIHBhaXIgKGEsIGIpIGluIGEgbWF0Y2hpbmcsIHRoZSBjb3N0IG9mIHRoZSBwYWlyIGlzIGRlZmluZWQgdG8gYmUgdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gYSBhbmQgYi4gVGhlIGNvc3Qgb2YgYSBtYXRjaGluZyBpcyB0aGUgc3VtIG9mIHRoZSBjb3N0IG9mIGFsbCBwYWlycyBpbiB0aGUgbWF0Y2hpbmcuIEZvciBleGFtcGxlLCB0aGUgY29zdCBvZiB0aGUgbWF0Y2hpbmcgTTEgaXMgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHR3byBzZXRzIG9mIG51bWJlcnMsIGNvbXB1dGUgdGhlIG1pbmltdW0gY29zdCBtYXRjaGluZyBvZiB0aGUgdHdvIHNldHMuIEZvciBleGFtcGxlLCB0aGUgbWF0Y2hpbmcgTTEgaXMgYSBtaW5pbXVtIGNvc3QgbWF0Y2hpbmcgb2YgdGhlIGdpdmVuIHR3byBzZXRzIFMgYW5kIFQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0d28gaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyLCBuPHN1Yj4xPFwvc3ViPiwgaXMgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgZmlyc3Qgc2V0LCBhbmQgdGhlIHNlY29uZCBpbnRlZ2VyLCBuPHN1Yj4yPFwvc3ViPiwgaXMgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgc2Vjb25kIHNldCwgd2hlcmUgMSAmbGU7IG48c3ViPjE8XC9zdWI+LCBuPHN1Yj4yPFwvc3ViPiAmbGU7IDUwMCwwMDAuIFRoZSBzZWNvbmQgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBuPHN1Yj4xPFwvc3ViPiBpbnRlZ2VycyBmb3IgdGhlIGZpcnN0IHNldCBhbmQgdGhlIHRoaXJkIGxpbmUgY29udGFpbnMgbjxzdWI+MjxcL3N1Yj4gaW50ZWdlcnMgZm9yIHRoZSBzZWNvbmQgc2V0LiBUaGUgaW50ZWdlcnMgaW4gZWFjaCBzZXQgYXJlIGFycmFuZ2VkIGluIGluY3JlYXNpbmcgb3JkZXIuIEFsbCBpbnB1dCBpbnRlZ2VycyBhcmUgYmV0d2VlbiAwIGFuZCAxLDAwMCwwMDAsMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgY29zdCBvZiB0aGUgbWluaW11bSBjb3N0IG1hdGNoaW5nIG9mIHRoZSB0d28gc2V0cyBvZiBpbnRlZ2Vycy4mbmJzcDs8XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

  • 문제를 번역한 사람: author5