대도시

정보과학 Swedish Olympiad의 참가자들은 기하학을 좋아하며, 그럴 만한 이유가 있다. 여러 기하학 중 가장 인기 있는 것은 이른바 맨해튼 기하학이다. 정규 격자에서 두 점 P와 Q 사이의 맨해튼 거리는 수평과 수직으로만 이동할 수 있을 때 P에서 Q로 가기 위해 지나야 하는 간선의 수를 나타낸다.

P가 $= (x_1,y_1)$이고 Q가 $= (x_2,y_2)$이면, 두 점 사이의 맨해튼 거리는 $|x_1-x_2| + |y_1-y_2|$로 계산한다. 여기서 $|a|$는 수 $a$의 절댓값을 나타낸다. 즉, 수가 음수이면 마이너스 부호를 무시한다.

이제 여러분이 기하학을 얼마나 좋아하는지 보여 줄 차례다. 맨해튼 거리가 적용되는 대도시로 이사할 계획이다. 대도시에는 친구 $N$명이 살고 있지만, 선택할 수 있는 아파트는 $M$개뿐이다. 여러분의 임무는 아파트에서 $N$명의 모든 친구까지의 맨해튼 거리의 합이 가능한 한 작아지도록 아파트를 선택하는 방법을 알아내는 것이다.

[!h]

검은 점은 대도시에서 선택할 수 있는 아파트를 나타내고, 회색 점은 친구들이 사는 곳을 나타낸다. (0,0)에 있는 아파트를 선택하면 친구들까지의 거리의 합은 4+6+6+9=25가 된다. (1,6)에 있는 아파트를 선택하면 거리의 합은 3+5+6+9=23가 된다. 남은 아파트를 선택하면 거리의 합은 1+4+6+4=15가 되므로, (5,5)에 있는 아파트를 선택하는 것이 최적이다.

채점

제출한 풀이는 여러 테스트 그룹으로 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$40$| $N \leq 10{,}000, M \leq 100$

$2$ |$60$| 추가 제한 조건 없음.

입력의 첫째 줄에는 친구의 수와 선택할 수 있는 아파트의 수를 나타내는 두 정수 $N$와 $M$가 주어진다 ($1 \leq N, M \leq 10^5$).

이어서 친구들이 도시의 어느 교차로에 사는지를 나타내는 정수 쌍 $x_i$와 $y_i$가 $N$줄에 걸쳐 주어진다 ($-10{,}000 \leq x_i, y_i \leq 10{,}000$).

마지막으로 도시의 어느 교차로를 거주지로 선택할 수 있는지를 나타내는 정수 쌍 $x_i$와 $y_i$가 $M$줄에 걸쳐 주어진다 ($-10{,}000 \leq x_i, y_i \leq 10{,}000$). 대도시에는 고층 건물이 있을 수 있다는 점에 유의하라. 즉, 하나의 점이 입력에 여러 번 나타날 수 있다.

아파트에서 $N$명의 친구까지의 맨해튼 거리의 합으로 가능한 최솟값을 정수로 출력한다.

정답이 항상 $32$비트 정수에 들어맞는 것은 아니라는 점에 유의하라.