Fenced In (Gold)#10588

Fenced In (Gold)

1 second

128 megabytes

Hard

Farmer John has realized that many of his cows are strangely agoraphobic (that is, they are afraid of large open spaces). To make them less afraid of grazing, he partitions his large field into a number of smaller regions by building vertical (north-south) and horizontal (east-west) fences.

The large field is a rectangle with corner points at $(0, 0)$ and $(a, b)$ . FJ builds $n$ vertical fences at distinct positions $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a), with each fence running from $(a_{i}, 0)$ (a_i, 0) to $(a_{i}, b)$ (a_i, b). He also builds $m$ horizontal fences at positions $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b), with each fence running from $(0, b_{i})$ (0, b_i) to $(a, b_{i})$ (a, b_i). Each vertical fence crosses every horizontal fence, subdividing the large field into a total of $(n + 1) (m + 1)$ (n + 1)(m + 1) regions.

Unfortunately, FJ completely forgot to build gates into his fences, making it impossible for the cows to leave their enclosed regions and travel throughout the entire field! He wants to remedy this situation by removing portions of some of his fences, allowing cows to travel between adjacent regions. He wants to select certain pairs of adjacent regions and remove the entire length of the fence separating each pair. Afterward, he wants the cows to be able to pass through these openings and travel anywhere in the larger field.

For example, FJ might start with a fence pattern like this:

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

and open it up as follows:

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

Please help FJ determine the minimum total length of fencing he must remove to accomplish his goal.

Input

The first line contains four integers $a, b (1 \leq a, b \leq 1 0^{9}$ a, b~(1 \le a, b \le 10^9), $n (0 \leq n \leq 2000)$ n~(0 \le n \le 2000), and $m (0 \leq m \leq 2000)$ m~(0 \le m \le 2000). The next $n$ lines contain the values $a_{1}, \dots, a_{n} (0 < a_{i} < a)$ a_1, \ldots, a_n~(0 < a_i < a), and the following $m$ lines contain the values $b_{1}, \dots, b_{m} (0 < b_{i} < b)$ b_1, \ldots, b_m~(0 < b_i < b).

Output

Print the minimum total length of fencing that FJ must remove. Note that this value may be too large to fit in a standard $32$ -bit integer, so you may need to use a $64$ -bit integer type.

Examples

Example 1