Fenced In (Gold)

Farmer John has noticed that many of his cows are afraid of wide open spaces. To make grazing less frightening for them, he split his large field into smaller regions by building north to south (vertical) fences and east to west (horizontal) fences.

The field is a rectangle whose opposite corners are $(0,0)$ and $(A,B)$. Farmer John built $n$ vertical fences ($0 \le n \le 2000$) at distinct positions $a_1, \ldots, a_n$ ($0 < a_i < A$), and the fence at $a_i$ runs from $(a_i, 0)$ to $(a_i, B)$. He also built $m$ horizontal fences ($0 \le m \le 2000$) at distinct positions $b_1, \ldots, b_m$ ($0 < b_i < B$), and the fence at $b_i$ runs from $(0, b_i)$ to $(A, b_i)$. Every vertical fence crosses every horizontal fence, so the field is cut into $(n+1)(m+1)$ regions.

Farmer John forgot to put gates in his fences, so a cow cannot leave the region it stands in and walk around the whole field. He wants to fix that by removing pieces of some fences. He picks pairs of adjacent regions and removes the entire length of fence that separates them. After the removals a cow must be able to reach any region from any other region through the openings.

For example, a fence layout like this

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

can be opened up like this.

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

Find the minimum total length of fence Farmer John has to remove.

The first line has $A$, $B$, $n$, and $m$ ($1 \le A, B \le 10^9$). Each of the next $n$ lines has one of $a_1, \ldots, a_n$, and each of the $m$ lines after that has one of $b_1, \ldots, b_m$.

Print the minimum total length of fence Farmer John has to remove. The answer can exceed the range of a 32-bit integer, so you may need a 64-bit integer type (long long in C or C++, for example).