시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB132047235436.270%

문제

정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다.

A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자.

  • C[i] 는 배열 B에 있는 값 중 A[i] 에 가장 가까운 값 (절대값 차이가 가장 작은 값)으로 정의 된다. 
  • 만약 이 조건을 만족하는 값들이 여럿 있는 경우, 그 중 가장 크기가 작은 값으로 정의 된다.

예를 들어 A = [20, 5, 14, 9] 그리고 B = [16, 8, 12] 라고 해보자.

  • C[1] = 16 이다 - 왜냐하면 B[1] = 16이 A[1] = 20에 가장 가깝기 때문이다.
  • C[2] = 8 이다 - 왜냐하면 B[2] = 8이 A[2] = 5에 가장 가깝기 때문이다.
  • C[3] = 12 이다 - 왜냐하면 B[1] = 16 와 B[3] = 12 모두 A[3] = 14에 가장 가깝지만, B[3]의 값이 더 작기 때문이다.
  • C[4] = 8이다.

이 예제의 경우 C = [16, 8, 12, 8]으로 정의된다.

두 배열 A와 B가 주어졌을 때, 새로운 배열 C를 계산하여 배열 C에 포함된 값들의 합을 구하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 수 T (1 <= T <= 10)가 주어진다.

각 테스트 케이스는 세 줄에 걸쳐서 주어진다.

첫 줄에는 n과 m이 공백으로 구분되어 주어진다 (1 <= n, m <= 10^6).

두 번째 줄에는 공백으로 구분된 n개의 정수가 주어지며, A[1] 부터 A[n]을 나타낸다 (각각의 값은 1이상 10^9 이하이다).

세 번째 줄에는 공백으로 구분된 m개의 정수가 주어지며, B[1] 부터 B[m]을 나타낸다 (각각의 값은 1이상 10^9 이하이다).

앞서 언급한대로, A와 B는 각각 서로 다른 양의 정수들을 포함한 배열들이다.

출력

각 테스트 케이스에 대해 배열 C를 구하고 해당 배열의 모든 원소 합을 한 줄에 출력하시오.

예제 입력 1

3
4 3
20 5 14 9
16 8 12
3 4
16 8 12
20 5 14 9
3 3
1 2 3
2 3 4

예제 출력 1

44
37
7

힌트

첫 테스트 케이스는 문제에서 언급되었다.

두 번째 테스트 케이스의 경우 A = [16, 8, 12] 이고  B = [20, 5, 14, 9] 이다.

이 경우 배열 C는 [14, 9, 14] 이며 따라서 정답은 14+9+14 = 37이다.

세 번째 테스트의 경우 C = [2 2 3] 이며 정답은 7이다. 

W3sicHJvYmxlbV9pZCI6IjE3MTI0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJjMzBcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1YzIxOCBcdWJjMzBcdWM1ZjQgQSBcdWM2NDAgQlx1YWMwMCBcdWM3ODhcdWIyZTQuIEFcdWIyOTQgXHVjZDFkIG5cdWFjMWNcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBCXHViMjk0IFx1Y2QxZCBtXHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkEsIEJcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCBuXHVjNzc4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJjMzBcdWM1ZjQgQ1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q1tpXSBcdWIyOTQgXHViYzMwXHVjNWY0IEJcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMxMiBcdWM5MTEgQVtpXSBcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjMTIgKFx1YzgwOFx1YjMwMFx1YWMxMiBcdWNjMjhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjMTIpXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OCBcdWI0MWNcdWIyZTQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCBcdWM3NzQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMTJcdWI0ZTRcdWM3NzQgXHVjNWVjXHViN2ZmIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjAsIFx1YWRmOCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVhYzEyXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBBID0gWzIwLCA1LCAxNCwgOV0gXHVhZGY4XHViOWFjXHVhY2UwIEIgPSBbMTYsIDgsIDEyXSBcdWI3N2NcdWFjZTAgXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkNbMV0gPSAxNiBcdWM3NzRcdWIyZTQgLSBcdWM2NWNcdWIwZDBcdWQ1NThcdWJhNzQgQlsxXSA9IDE2XHVjNzc0IEFbMV0gPSAyMFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTVkXHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+Q1syXSA9IDggXHVjNzc0XHViMmU0IC0gXHVjNjVjXHViMGQwXHVkNTU4XHViYTc0IEJbMl0gPSA4XHVjNzc0IEFbMl0gPSA1XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNWRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5DWzNdID0gMTIgXHVjNzc0XHViMmU0IC0gXHVjNjVjXHViMGQwXHVkNTU4XHViYTc0IEJbMV0gPSAxNiBcdWM2NDAgQlszXSA9IDEyIFx1YmFhOFx1YjQ1MCBBWzNdID0gMTRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU1ZFx1YzljMFx1YjljYywgQlszXVx1Yzc1OCBcdWFjMTJcdWM3NzQgXHViMzU0IFx1Yzc5MVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPkNbNF0gPSA4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwIEMgPSBbMTYsIDgsIDEyLCA4XVx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjMzBcdWM1ZjQgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJjMzBcdWM1ZjQgQ1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWM1ZWMgXHViYzMwXHVjNWY0IENcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YWMxMlx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFQgKDEgJmx0Oz0gVCAmbHQ7PSAxMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMxMzggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWNmYyBtXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsdDs9IG4sIG0gJmx0Oz0gMTBeNikuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgblx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBBWzFdIFx1YmQ4MFx1ZDEzMCBBW25dXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNCAoXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWMxMlx1Yzc0MCAxXHVjNzc0XHVjMGMxIDEwXjkgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0KS48XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBtXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIEJbMV0gXHViZDgwXHVkMTMwIEJbbV1cdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0IChcdWFjMDFcdWFjMDFcdWM3NTggXHVhYzEyXHVjNzQwIDFcdWM3NzRcdWMwYzEgMTBeOSBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQpLjxcL3A+XHJcblxyXG48cD5cdWM1NWVcdWMxMWMgXHVjNWI4XHVhZTA5XHVkNTVjXHViMzAwXHViODVjLCBBXHVjNjQwIEJcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWMgXHViYzMwXHVjNWY0XHViNGU0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWJjMzBcdWM1ZjQgQ1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWFjZTAgXHVkNTc0XHViMmY5IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjIFx1ZDU2OVx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzViOFx1YWUwOVx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWNiZFx1YzZiMCBBID0gWzE2LCA4LCAxMl0gXHVjNzc0XHVhY2UwICZuYnNwO0IgPSBbMjAsIDUsIDE0LCA5XSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjYmRcdWM2YjAgXHViYzMwXHVjNWY0IENcdWIyOTQgWzE0LCA5LCAxNF0gXHVjNzc0XHViYTcwIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM4MTVcdWIyZjVcdWM3NDAgMTQrOSsxNCA9IDM3XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Yzc1OCBcdWFjYmRcdWM2YjAgQyA9IFsyIDIgM10gXHVjNzc0XHViYTcwIFx1YzgxNVx1YjJmNVx1Yzc0MCA3XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTcxMjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUd28gQXJyYXlzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgdHdvIGFycmF5cywgQSBhbmQgQiwgZWFjaCBjb250YWluaW5nIGRpc3RpbmN0IHBvc2l0aXZlIGludGVnZXJzIHdpdGggbGVuZ3RoIG4gYW5kIG0gcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5PdXIgZ29hbCBpcyB0byBjb25zdHJ1Y3QgYXJyYXkgQywgd2l0aCBsZW5ndGggbiwgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggaSwgQ1tpXSBpcyBhbiBlbGVtZW50IG9mIEIgdGhhdCBpcyBjbG9zZXN0IHRvIEFbaV0gKGluIGFic29sdXRlIGRpZmZlcmVuY2UpPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBtdWx0aXBsZSBwb3NzaWJsZSB2YWx1ZXMsIGNob29zZSB0aGUgc21hbGxlc3Qgb25lLjxcL3A+XHJcblxyXG48cD5Gb3IgaW5zdGFuY2UsIGNvbnNpZGVyIEEgPSBbMjAsIDUsIDE0LCA5XSBhbmQgQiA9IFsxNiwgOCwgMTJdLDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkNbMV0gPSAxNiBiZWNhdXNlIEJbMV0gPSAxNiBpcyBjbG9zZXN0IHRvIEFbMV0gPSAyMC48XC9saT5cclxuXHQ8bGk+Q1syXSA9IDggYmVjYXVzZSBCWzJdID0gOCBpcyBjbG9zZXN0IHRvIEFbMl0gPSA1LjxcL2xpPlxyXG5cdDxsaT5DWzNdID0gMTIgYmVjYXVzZSBib3RoIEJbMV0gPSAxNiBhbmQgQlszXSA9IDEyIGFyZSBlcXVhbGx5IGNsb3NlIHRvIEFbM10gPSAxNCwgYnV0IEJbM10gaXMgc21hbGxlci48XC9saT5cclxuXHQ8bGk+Q1s0XSA9IDguPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SGVuY2UgaW4gdGhpcyBjYXNlIHdlIGhhdmUgQyA9IFsxNiwgOCwgMTIsIDhdLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gYXJyYXlzIEEgYW5kIEIsIGNvbnN0cnVjdCBhbiBhcnJheSBDIGFzIGFib3ZlLCBhbmQgb3V0cHV0IHRoZSBzdW0gb2YgYWxsIGVsZW1lbnRzIGluIEMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdGhlIG51bWJlciBvZiB0ZXN0IGNhc2UgVCAoMSAmbHQ7PSBUICZsdDs9IDEwKS48XC9wPlxyXG5cclxuPHA+QSBzaW5nbGUgdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzOjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzIG4gYW5kIG0gKDEgJmx0Oz0gbiwgbSAmbHQ7PSAxMF42KS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIHdpbGwgY29udGFpbiBuIGludGVnZXJzIChkZWxpbWl0ZWQgYnkgd2hpdGVzcGFjZSkgcmVwcmVzZW50aW5nIEFbMV0gdG8gQVtuXSAoYmV0d2VlbiAxIGFuZCAxMF45LCBpbmNsdXNpdmUpLjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSB3aWxsIGNvbnRhaW4gbSBpbnRlZ2VycyAoZGVsaW1pdGVkIGJ5IHdoaXRlc3BhY2UpIHJlcHJlc2VudGluZyBCWzFdIHRvIEJbbV0gKGJldHdlZW4gMSBhbmQgMTBeOSwgaW5jbHVzaXZlKS48XC9wPlxyXG5cclxuPHA+UmVjYWxsIHRoYXQgQSBjb250YWlucyBkaXN0aW5jdCBpbnRlZ2VycyBhbmQgQiBjb250YWlucyBkaXN0aW5jdCBpbnRlZ2Vycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGNvbXB1dGUgdGhlIGFycmF5IEMgYW5kIG91dHB1dCB0aGUgc3VtIG9mIGVsZW1lbnRzIGluIEMuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmaXJzdCBjYXNlIHdhcyBleHBsYWluZWQgaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LjxcL3A+XHJcblxyXG48cD5JbiB0aGUgc2Vjb25kIGNhc2UsIHdlIGhhdmUgQSA9IFsxNiwgOCwgMTJdIGFuZCBCID0gWzIwLCA1LCAxNCwgOV0uIEMgaXMgdGhlbiBbMTQsIDksIDE0XSBhbmQgdGhlcmVmb3JlIHRoZSBhbnN3ZXIgaXMgMzcuPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgdGhpcmQgY2FzZSwgd2UgaGF2ZSBDID0gWzIgMiAzXSBhbmQgdGhlIGFuc3dlciBpcyA3LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==