Олимпиадный тренинг

Задача 29546. Fenced In


Задача

Темы:
Farmer John's cows are afraid of large spaces. Therefore, I divided my field into a number of small regions, building vertical (north-south) and horizontal (east-west) fences.
The field is a rectangle with corner vertices at points (0,0) and (A,B). The FD built n vertical fences (0≤n≤25,000) at different positions a1…an (0<ai<A ); each fence runs from point (ai,0) to point (ai,B). He also built m horizontal hedges (0≤m≤25,000) at different positions b1…bm (0<bi<B); each hedge going from (0,bi) to (A,bi). Each vertical hedge intersects with each horizontal hedge, dividing the field into (n+1)(m+1) regions.
 
Unfortunately, the FD forgot to build a gate in his hedges, making it impossible for the cows to leave their region. He wants to remedy the situation by removing pieces of the hedge to allow the cows to move between neighboring regions. He wants to select some pairs of adjacent regions and remove the entire length of the fence between them. He also wants to ensure that the cows can get into any part of the field.
 
For example, the FD could build fences like this:
 
+---+--+
|      |   |
+---+--+
|     |    |  
|     |    |
+---+--+
and open them like this:
 
+---+--+
|          |  
+---+  +  
|          |  
|          |
+---+--+
Help the FD determine the minimum total length of hedges he must remove to reach his goal.

INPUT FORMAT:
The first input line contains the numbers A, B, n, and m (1≤A,B≤1,000,000,000). The next n lines contain a1…an. The next m lines contain b1…bm.

OUTPUT FORMAT:
Print the minimum length of the fence that the FD must remove. Note that this number may not fit in a 32-bit integer and you need to use a 64-bit integer (e.g. "long long" in C/C++ )

Enter Output
15 15 5 2
2
5
10
6
4
11
3
44