Minimum Fence Removal

Farmer John has recently discovered that his cows suffer from a fear of large, open spaces. To ease their anxiety, he divided his rectangular pasture (with opposite corners at \( (0,0) \) and \( (A,B) \)) into multiple small regions by building fences. He placed vertical fences at \(a_1, a_2, \ldots, a_n\) (each running from \( (a_i,0) \) to \( (a_i,B) \)) and horizontal fences at \(b_1, b_2, \ldots, b_m\) (each running from \( (0,b_i) \) to \( (A,b_i) \)). These fences subdivide the pasture into \((n+1)(m+1)\) regions.

Unfortunately, because Farmer John forgot to install gates, the cows are trapped in their individual regions. To solve this problem, he can remove the fence that separates two adjacent regions (that is, regions sharing a common fence segment). Removing a fence segment has a cost equal to its length. In particular, if the fence between two horizontally adjacent regions is removed, the cost is the height of that region; if the fence between two vertically adjacent regions is removed, the cost is the width of that region.

Your task is to help Farmer John choose which fences to remove such that all regions become connected (i.e. one can travel between any two regions) while minimizing the total removal cost. Formally, if we denote by
\(w_i\) the width of the \(i\)-th column (for \(i=0,1,\ldots,n\)), where \(w_0 = a_1 - 0,\;w_i = a_{i+1} - a_i\) for \(1 \le i \le n-1,\) and \(w_n = A - a_n,\)
and by
\(h_j\) the height of the \(j\)-th row (for \(j=0,1,\ldots,m\)), where \(h_0 = b_1 - 0,\;h_j = b_{j+1} - b_j\) for \(1 \le j \le m-1,\) and \(h_m = B - b_m,\)
then every removal operation on a fence between two horizontally adjacent regions costs \(h_j\) (if the regions are in the \(j\)-th row) and every removal on a fence between two vertically adjacent regions costs \(w_i\) (if the regions are in the \(i\)-th column).

This can be modeled as finding a minimum spanning tree on a grid graph where each node represents a region and the edges between adjacent regions have weights as described. Solve for the minimum total cost required to connect all regions.

inputFormat

The input consists of four lines:

• The first line contains two integers \(A\) and \(B\): the dimensions of the pasture.
• The second line contains two integers \(n\) and \(m\): the number of vertical and horizontal fences, respectively.
• The third line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\) (in any order) representing the x-coordinates where vertical fences are built.
• The fourth line contains \(m\) distinct integers \(b_1, b_2, \ldots, b_m\) (in any order) representing the y-coordinates where horizontal fences are built.

outputFormat

Output a single integer representing the minimum total length of fences that must be removed so that the entire pasture becomes connected.

sample

10 10
1 1
4
5

14