Fenced In (Platinum)#10590

Fenced In (Platinum)

1 second

128 megabytes

Very 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); each fence runs 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); each fence runs 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) \times (m + 1)$ (n + 1) \times (m + 1) regions.

Unfortunately, FJ completely forgot to build gates into his fences, making it impossible for 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 to allow cows to travel between adjacent regions. He wants to select certain pairs of adjacent regions and remove the entire length of fence separating each pair. Afterwards, he wants the cows to be able to wander through these openings so that they can 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 25000)$ n~(0 \le n \le 25000), and $m (0 \leq m \leq 25000)$ m~(0 \le m \le 25000). The next $n$ lines contain $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, and the following $m$ lines contain $b_{1}, \dots, b_{m}$ b_1, \ldots, b_m.

Output

Print the minimum total length of fencing 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