울타리 안에서

농부 존은 자신의 소 상당수가 이상하게도 광장 공포증(넓은 열린 공간을 두려워하는 증상)이 있다는 것을 알게 되었다. 소들이 풀 뜯기를 덜 무서워하게 하려고, 그는 수직(남북) 울타리와 수평(동서) 울타리를 세워 넓은 밭을 여러 개의 작은 영역으로 나눈다.

넓은 밭은 꼭짓점이 \((0,0)\)과 \((A,B)\)인 직사각형이다. 농부 존은 서로 다른 위치 \(a_1 \ldots a_n\) (\(0 < a_i < A\))에 수직 울타리 \(n\)개를 세운다 (\(0 \leq n \leq 25,000\)). 각 울타리는 \((a_i, 0)\)에서 \((a_i, B)\)까지 이어진다. 또한 위치 \(b_1 \ldots b_m\) (\(0 < b_i < B\))에 수평 울타리 \(m\)개를 세운다 (\(0 \leq m \leq 25,000\)). 각 울타리는 \((0, b_i)\)에서 \((A, b_i)\)까지 이어진다. 각 수직 울타리는 각 수평 울타리를 가로지르며, 넓은 밭을 총 \((n+1)(m+1)\)개의 영역으로 나눈다.

안타깝게도 농부 존은 울타리에 문을 만드는 것을 완전히 잊어버려서, 소들이 자신이 갇힌 영역을 벗어나 밭 전체를 돌아다니는 것이 불가능해졌다! 그는 소들이 인접한 영역 사이를 오갈 수 있도록 일부 울타리의 조각을 제거하여 이 상황을 바로잡으려 한다. 인접한 영역 쌍을 몇 개 골라 그 사이를 가르는 울타리 전체 길이를 제거하고, 그 뒤에는 소들이 이 통로들을 지나다니며 넓은 밭 어디든 갈 수 있기를 원한다.

예를 들어, 농부 존은 다음과 같은 울타리 배치를

+---+--+
|   |  |
+---+--+
|   |  |
|   |  |
+---+--+

다음과 같이 열 수 있다.

+---+--+
|      |
+---+  +
|      |
|      |
+---+--+

농부 존이 목표를 달성하기 위해 제거해야 하는 울타리의 최소 총길이를 구하는 것을 도와주자.

출제자: Brian Dean

출제자: Brian Dean

입력의 첫째 줄에 \(A\), \(B\), \(n\), \(m\)이 주어진다 (\(1 \leq A, B \leq 1,000,000,000\)). 다음 \(n\)개의 줄에 \(a_1 \ldots a_n\)이, 그다음 \(m\)개의 줄에 \(b_1 \ldots b_m\)이 주어진다.

농부 존이 제거해야 하는 울타리의 최소 길이를 출력한다. 이 값은 표준 32비트 정수에 담기에 너무 클 수 있으므로, 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수도 있음에 유의하자.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > February > Platinum