시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15 15 15 100.000%

문제

음 아닌 정수들로 이루어진 두 개의 집합 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의 원소가 첫째 줄에 주어진 개수만큼 빈 칸을 사이에 두고 증가하는 순서대로 주어진다. 각 집합의 원소의 크기는 50,000 이하의 자연수이며, 주어지는 수는 0 이상 100,000 이하의 정수이다.

출력

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

예제 입력 1

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

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjE2MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc0YyBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzlkMVx1ZDU2OSBTXHVjNjQwIFRcdWFjMDAgXHVjNzg4XHViMmU0LiBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1YWNmYyBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM5ZGRcdWM5YzBcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5TXHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM2ZDBcdWMxOGMgc1x1YjI5NCBUXHVjNzU4IFx1YzViNFx1YjVhNCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIzYzQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMFx1ZDU1YyBUXHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM2ZDBcdWMxOGMgdFx1YjNjNCBTXHVjNzU4IFx1YzViNFx1YjVhNCBcdWM2ZDBcdWMxOGNcdWM2NDBcdWIzYzQgXHVjOWRkXHVjOWMwXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlNcdWM3NTggXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHVjNzU4IFRcdWM3NTggXHVjNmQwXHVjMThjXHVjNjQwXHViMjk0IFx1YzlkZFx1YzljMFx1YzViNFx1YzgzOFx1YzU3YyBcdWQ1NThcdWFjZTAsIFRcdWM3NTggXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4YyBcdWM1ZWRcdWMyZGMgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YzY0MFx1YjI5NCBcdWM5ZGRcdWM5YzBcdWM1YjRcdWM4MzhcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgUz17MiwgOCwgOSwgMTAsIDExfSwgVD17MCwgMywgNCwgNiwgNywgMTF9XHVjNzQ0IFx1YmNmNFx1Yzc5MC4geygyLCAwKSwgKDIsIDMpLCAoMiwgNCksICg4LCA2KSwgKDksIDcpLCAoMTAsIDExKSwgKDExLCAxMSl9XHVjNzQwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIHsoMiwgMCksICg4LCAzKSwgKDksIDQpLCAoMTAsIDYpLCAoMTEsIDcpfVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1NDRcdWIyY2NcdWIzNzAsIFRcdWM3NTggXHVjNmQwXHVjMThjIDExXHVjNzc0IFNcdWM3NTggXHVjNWI0XHViNWE0IFx1YzZkMFx1YzE4Y1x1YzY0MFx1YjNjNCBcdWM5ZGRcdWM5YzBcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YzlkZCAoYSwgYilcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzc0XHViNzgwLCBhXHVjNjQwIGJcdWM3NTggXHVjYzI4XHVjNzc0XHVjNzU4IFx1YzgwOFx1YjMxM1x1YWMxMlx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWJhYThcdWI0ZTAgXHViZTQ0XHVjNmE5XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViM2M0XHViODVkIFNcdWM3NTggXHVjNmQwXHVjMThjXHViNGU0XHVhY2ZjIFRcdWM3NTggXHVjNmQwXHVjMThjXHViNGU0XHVjNzQ0IFx1YzlkZFx1YzljMFx1YzczY1x1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgU1x1YzY0MCBUXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCAxMFx1Yzc3NCBcdWNkNWNcdWMxOGNcdWM3NTggXHViZTQ0XHVjNmE5XHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+U1x1YzY0MCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHViYWE4XHViNGUwIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjNjNFx1Yjg1ZCBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1YWNmYyBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM5ZGRcdWM5YzBcdWM1YjQgXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFNcdWM3NTggXHVjNmQwXHVjMThjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBTXHVjNzU4IFx1YzZkMFx1YzE4YywgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBUXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjMWNcdWMyMThcdWI5Y2NcdWQwN2MgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOWQxXHVkNTY5XHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgNTAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWJhNzAsIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgMCBcdWM3NzRcdWMwYzEgMTAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjMThjXHVjNzU4IFx1YmU0NFx1YzZhOVx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTYyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik51bWJlciIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIGdpdmVuIHR3byBzZXRzIFMgYW5kIFQgb2YgbnVtYmVycywgbGV0IGEgbWF0Y2hpbmcgb2YgUyBhbmQgVCBiZSBhIHNldCBvZiBwYWlycyAocywgdCksIHMmaXNpbjtTLCB0JmlzaW47VCBzdWNoIHRoYXQgZWFjaCBudW1iZXIgaW4gUyBpcyBwYWlyZWQgd2l0aCBhdCBsZWFzdCBvbmUgbnVtYmVyIGluIFQgYW5kIGVhY2ggbnVtYmVyIGluIFQgaXMgcGFpcmVkIHdpdGggYXQgbGVhc3Qgb25lIG51bWJlciBpbiBTLiBGb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyBpcyBhIG1hdGNoaW5nIG9mIHR3byBzZXRzIFM9ezIsIDgsIDksIDEwLCAxMX0sIFQ9ezAsIDMsIDQsIDYsIDcsIDExfTombmJzcDs8XC9wPlxyXG5cclxuPHA+TTEgPXsoMiwgMCksICgyLCAzKSwgKDIsIDQpLCAoOCwgNiksICg5LCA3KSwgKDEwLCAxMSksICgxMSwgMTEpfTxcL3A+XHJcblxyXG48cD5XaGVyZWFzIHRoZSBmb2xsb3dpbmcgaXMgbm90IGEgbWF0Y2hpbmcgb2YgUyBhbmQgVCwmbmJzcDs8XC9wPlxyXG5cclxuPHA+TTIgPXsoMiwgMCksICg4LCAzKSwgKDksIDQpLCAoMTAsIDYpLCAoMTEsIDcpfSZuYnNwOzxcL3A+XHJcblxyXG48cD5zaW5jZSB0aGUgbnVtYmVyIDExIGluIHNldCBUIGlzIG5vdCBwYWlyZWQgd2l0aCBhbnkgbnVtYmVyIGluIFMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBhIHBhaXIgKGEsIGIpIGluIGEgbWF0Y2hpbmcsIHRoZSBjb3N0IG9mIHRoZSBwYWlyIGlzIGRlZmluZWQgdG8gYmUgdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gYSBhbmQgYi4gVGhlIGNvc3Qgb2YgYSBtYXRjaGluZyBpcyB0aGUgc3VtIG9mIHRoZSBjb3N0IG9mIGFsbCBwYWlycyBpbiB0aGUgbWF0Y2hpbmcuIEZvciBleGFtcGxlLCB0aGUgY29zdCBvZiB0aGUgbWF0Y2hpbmcgTTEgaXMgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHR3byBzZXRzIG9mIG51bWJlcnMsIGNvbXB1dGUgdGhlIG1pbmltdW0gY29zdCBtYXRjaGluZyBvZiB0aGUgdHdvIHNldHMuIEZvciBleGFtcGxlLCB0aGUgbWF0Y2hpbmcgTTEgaXMgYSBtaW5pbXVtIGNvc3QgbWF0Y2hpbmcgb2YgdGhlIGdpdmVuIHR3byBzZXRzIFMgYW5kIFQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0d28gaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyLCBuPHN1Yj4xPFwvc3ViPiwgaXMgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgZmlyc3Qgc2V0LCBhbmQgdGhlIHNlY29uZCBpbnRlZ2VyLCBuPHN1Yj4yPFwvc3ViPiwgaXMgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgc2Vjb25kIHNldCwgd2hlcmUgMSAmbGU7IG48c3ViPjE8XC9zdWI+LCBuPHN1Yj4yPFwvc3ViPiAmbGU7IDUwLDAwMC4gVGhlIHNlY29uZCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIG48c3ViPjE8XC9zdWI+IGludGVnZXJzIGZvciB0aGUgZmlyc3Qgc2V0IGFuZCB0aGUgdGhpcmQgbGluZSBjb250YWlucyBuPHN1Yj4yPFwvc3ViPiBpbnRlZ2VycyBmb3IgdGhlIHNlY29uZCBzZXQuIFRoZSBpbnRlZ2VycyBpbiBlYWNoIHNldCBhcmUgYXJyYW5nZWQgaW4gaW5jcmVhc2luZyBvcmRlci4gQWxsIGlucHV0IGludGVnZXJzIGFyZSBiZXR3ZWVuIDAgYW5kIDEwMCwwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBjb3N0IG9mIHRoZSBtaW5pbXVtIGNvc3QgbWF0Y2hpbmcgb2YgdGhlIHR3byBzZXRzIG9mIGludGVnZXJzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==