Fenced In timer 2s memory 512MB

농부 John은 자신의 소들이 넓은 들판을 무서워한다는 사실을 깨달았습니다. 이를 극복하기 위해 John은 큰 들판을 여러 개의 작은 구역으로 나누기 위해 남북 방향의 세로 울타리와 동서 방향의 가로 울타리를 건설합니다.
큰 들판은 점 (0,0)과 (A,B)를 꼭짓점으로 하는 직사각형입니다. John은 서로 다른 위치에 n (0 \leq n \leq 25,000)개의 세로 울타리를 건설하는데, 이들 울타리는 각각 (a_i,0)에서 (a_i,B)까지 이어지며 (0 < a_i < A). 또한, m (0 \leq m \leq 25,000)개의 가로 울타리를 건설하는데, 이들 울타리는 각각 (0,b_i)에서 (A,b_i)까지 이어지며 (0 < b_i < B). 세로 울타리와 가로 울타리가 서로 교차하면서 큰 들판은 총 (n+1)(m+1) 개의 구역으로 나뉘게 됩니다.

그러나 John은 울타리에 문(출입구)을 설치하는 것을 완전히 잊어버려, 소들이 자신의 구역을 벗어나 들판 전체를 돌아다닐 수 없게 되었습니다. 이를 해결하기 위해 John은 인접한 구역들 사이의 울타리 일부를 완전히 제거하여, 소들이 그 틈을 통해 자유롭게 이동할 수 있도록 하려 합니다. 구체적으로, 일부 인접한 두 구역 사이에 있는 울타리의 전체 길이를 제거하여 두 구역이 연결되게 만들고자 합니다.
John의 목표는, 이렇게 선택된 인접 구역 쌍에 대해 울타리 제거 작업을 수행한 후, 모든 구역이 서로 연결되어 소들이 들판 전체를 자유롭게 돌아다닐 수 있게 하는 것입니다. 이때, 제거해야 하는 울타리 길이의 총합을 최소화하고자 합니다.
문제는, 주어진 A, B, n, m과 울타리 위치 a_1,\ldots,a_n​, b_1,\ldots,b_m​에 대해, John이 목표를 달성하기 위해 제거해야 하는 울타리 길이의 최소 총합을 구하는 것입니다.

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

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