Minimal Fence Removal for Full Connectivity

Farmer John has built a set of fences in his rectangular pasture to divide it into many small regions. The pasture has two opposite corners at \( (0,0) \) and \( (A,B) \). He has installed \( n \) vertical fences at distinct positions \( a_1, a_2, \dots, a_n \) (each extending from \( (a_i,0) \) to \( (a_i,B) \)) and \( m \) horizontal fences at distinct positions \( b_1, b_2, \dots, b_m \) (each extending from \( (0,b_j) \) to \( (A,b_j) \)). These fences divide the pasture into \( (n+1)(m+1) \) regions, and, unfortunately, the fences have no gates so the cows in each region are isolated.

In order to let his cows roam freely over the entire field, Farmer John can remove individual fence segments. In one move, he may choose two adjacent regions (sharing a common fence segment) and remove the fence segment between them. The cost of removing a fence segment is equal to its length. More precisely:

• If two regions share a portion of a vertical fence, the removal cost is the vertical length of that segment. Note that the vertical fence is partitioned by the horizontal fences, so the length of the segment is equal to the difference between two consecutive \( y \)-coordinates.
• If two regions share a portion of a horizontal fence, the removal cost is the horizontal length of that segment (the difference between two consecutive \( x \)-coordinates).

After some fence removals, if the cows can travel from any region to any other region, the pasture is considered fully connected. Farmer John wants to achieve this connectivity with the minimum total fence removal cost.

Input Note: Let the sorted vertical boundaries be \( x_0=0, x_1, \dots, x_{n+1}=A \) (where \( x_1,\dots,x_n \) are the fence positions \( a_i \)) and the sorted horizontal boundaries be \( y_0=0, y_1, \dots, y_{m+1}=B \) (where \( y_1,\dots,y_m \) are the fence positions \( b_j \)). Then every cell (or region) is the rectangle \( [x_i,x_{i+1}]\times[y_j,y_{j+1}] \). The cost to remove the fence between two horizontally adjacent cells (i.e. same row) is \( y_{j+1}-y_j \), and the cost to remove the fence between two vertically adjacent cells (i.e. same column) is \( x_{i+1}-x_i \).

Your task is to compute the minimum total cost to remove a set of fence segments so that the entire pasture becomes connected.

It can be shown that this problem is equivalent to finding a minimum spanning tree (MST) in a grid graph where each cell is a vertex and the edge weights are given as above.

inputFormat

The input consists of four lines:

• The first line contains two integers \( A \) and \( B \) representing the dimensions of the pasture.
• The second line contains two integers \( n \) and \( m \) which denote the number of vertical and horizontal fences, respectively.
• The third line contains \( n \) distinct integers \( a_1, a_2, \dots, a_n \) (\(0 < a_i < A\)) specifying the \( x \)-positions of the vertical fences.
• The fourth line contains \( m \) distinct integers \( b_1, b_2, \dots, b_m \) (\(0 < b_j < B\)) specifying the \( y \)-positions of the horizontal fences.

You may assume that all numbers are positive integers.

outputFormat

Output a single integer: the minimum total length of fence segments that need to be removed to ensure that all regions are connected.

sample

10 5
1 1
4
2

9