영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
The contestants of the Swedish Olympiad in Informatics love geometry, and rightly so. The greatest favourite among the geometries is the so-called Manhattan geometry. The Manhattan distance between two points P and Q in a regular grid describes how many edges you have to traverse to get from P to Q, given that you may only move horizontally and vertically.
If P = (x_1,y_1) and Q = (x_2,y_2), the Manhattan distance between the points is computed as |x_1-x_2| + |y_1-y_2|. Here |a| denotes the absolute value of the number a, that is, we ignore the minus sign if the number is negative.
Now it is time for you to show how much you love geometry. You are planning your move to a metropolis where Manhattan distances apply. You have N friends living in the metropolis, but you only have M apartments to choose between. Your task is to figure out how to choose an apartment so that the sum of the Manhattan distances from your apartment to all of your N friends is as small as possible.
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The black dots represent the apartments we can choose between in the metropolis, and the grey dots mark where our friends live. If we choose the apartment at (0,0), the sum of the distances to the friends becomes 4+6+6+9=25. If we choose the apartment at (1,6), the sum of the distances becomes 3+5+6+9=23. If we choose the remaining apartment, the sum of the distances becomes 1+4+6+4=15, so choosing the apartment at (5,5) is optimal.
Input
The first line of input contains two integers N and M (1 ≤ N, M ≤ 10^5), the number of friends and the number of apartments you can choose between.
Then follow N lines with pairs of integers x_i and y_i (-10,000 ≤ x_i, y_i ≤ 10,000), describing at which intersections in the city your friends live.
Finally follow M lines with pairs of integers x_i and y_i (-10,000 ≤ x_i, y_i ≤ 10,000), describing at which intersections in the city you can choose to live. Note that there may be high-rise buildings in the metropolis (a point can occur several times in the input).
Output
Print an integer: the smallest possible sum of the Manhattan distances from your apartment to your N friends.
Note that the answer does not always fit in a 32-bit integer.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 40 | N ≤ 10,000, M ≤ 100 |
| 2 | 60 | No additional constraints. |
예제
예제 1
4 3 2 2 5 4 2 4 5 1 5 5 0 0 1 6
15
예제 2
2 2 0 0 0 2 2 0 2 2
6
예제 3
1 1 1 1 1 1
0