Description

Farmer John has realized that his cows have recently developed a phobia of overly open spaces. To reduce their fear while grazing, FJ decides to build some horizontal and vertical fences in the pasture to divide it into smaller regions.

The entire pasture is a rectangle with corners at $(0, 0)$ and $(A, B)$. FJ builds vertical fences at $n$ distinct positions $a_1, \ldots, a_n$, each from $(a_i, 0)$ to $(a_i, B)$; he builds horizontal fences at $m$ distinct positions $b_1, \ldots, b_m$, each from $(0, b_i)$ to $(A, b_i)$. The vertical and horizontal fences intersect pairwise, dividing the entire pasture into $(n+1)(m+1)$ regions.

Unfortunately, FJ forgot to add gates in the fences, so the cows are trapped in individual small regions. He can fix this by removing some fences. Each time, he can choose two adjacent regions and remove the fence that separates them. FJ’s goal is to allow the cows to reach any location in the pasture.

Here is an example:

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

After removing some fences:

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

To minimize the work, FJ wants the total length of removed fences to be as small as possible.

Input Format

The first line contains four integers $A, B, n, m$, with $1 \leq n, m \leq 2.5 \times 10^5$ and $1 \leq A, B \leq 10^9$.

The next $n$ lines each contain an integer $a_i$, with $0 \lt a_i \lt A$.

The next $m$ lines each contain an integer $b_i$, with $0 \lt b_i \lt B$.

Output Format

Output the minimum total length of fences to remove. The answer needs to be stored in a 64-bit signed integer.

15 15 5 2
2
5
10
6
4
11
3

44

Hint

Translated by ChatGPT 5