루미 알고리즘

#1320플래티넘Metropolis

PO 2013 결선코딩출제 Oskar Werkelin Ahlin영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
140N ≤ 10,000, M ≤ 100
260No 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

출처 표기

출처: Programmeringsolympiaden 2013년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.