KOI시는 너무나 커다라서, 이동하려면 시간이 오래 걸린다. 그래서 KOI시는 도시를 관통하는 아주 긴 도로를 건설하였다.

도로는 남북 방향 또는 동서 방향으로 무한히 뻗어 나간다. 남북 방향의 도로는 총 N개이고, 동서 방향의 도로는 총 M개이다. 도로의 폭은 충분히 좁아 무시할 수 있다.

KOI시의 시청을 원점으로 삼아 도시를 좌표평면 위에 그리면 남북 방향 도로는 x = a_i (1 \le i \le N)인 직선으로, 동서 방향 도로는 y = b_j (1 \le j \le M)인 직선으로 표현할 수 있다.

아래는 x = 3인 도로와 y = 2인 도로의 예이다. 그림에서는 도로가 유한하지만, 실제로는 무한히 뻗어 나감에 주의하라.

N + M개의 도로 중 K개의 도로에는 과속을 단속하기 위해 담당 경찰을 정확히 한 명씩 배치하였다. k (1 \le k \le N+M)번째 경찰의 위치는 (p_k, q_k)이다.

담당 경찰은 반드시 자신이 담당하는 도로 위에 위치한다.

아래는 x = 3 도로의, (3, -2) 지점에 경찰이 배치되고, y = 2 도로의 (-4, 2) 지점에 경찰이 배치된 예이다.

경찰이 배치 되지 않은 도로가 있을 수 있고, 어떤 도로에 경찰이 배치 되었다면 반드시 한 명이라는 것에 주의하라.

경찰은 도로 위를 이동할 수 있다. 경찰은 도로 위에서만 움직인다. 만약 두 도로가 교차한다면, 경찰은 그 지점에서 다른 도로로 옮겨갈 수 있다. 옮겨가는 데 드는 거리는 무시한다.

아래는 경찰이 다른 경찰의 위치로 움직이는 예시로, 이 경우에 경찰은 교점 (3, 2) 위에서 x = 3 직선을 나와 y = 2로 옮겨가게 된다. 총 11만큼 이동하였다.

경찰들은 만약의 사태에 다른 경찰과 빠르게 만날 수 있어야 한다. 당신은 각 경찰이 다른 경찰과 만나는 모든 경우에 대해 경찰의 최소 이동 거리를 구하여 그 합을 계산해야 한다. 아래 예시를 보자.

이 경우에는 총 3가지 경우가 있다.

따라서 총합은 26이 된다. x좌표가 -4인 경찰이 두 명 존재하지만, 경찰 (-4, 2)는 도로 y = 2에 있고 경찰 (-4, -1)은 도로 x = -4 위에 있으므로 유효한 입력임에 주의하라.

KOI시의 도로와 경찰들의 위치가 주어질 때, 위와 같이 두 경찰이 만나는 모든 경우에 대해 최소 이동 거리의 합을 출력하는 프로그램을 작성하라.

커다란 도시 timer 3s memory 1024MB

커다란 도시 3s 1024MB