P6171 [USACO16FEB] Fenced In G

*This problem has the same meaning as the [Platinum problem with the same name](/problem/P3141). The only difference is the Constraints.*

Farmer John realized that his cows have recently developed a phobia (fear of overly open spaces). To reduce their fear while grazing, FJ decided to build some horizontal and vertical fences to divide the pasture into several smaller regions. The whole pasture is a rectangle, with two corners at $(0,0)$ and $(A,B)$. FJ builds $n$ vertical fences at $n$ distinct positions $a_1,\ldots,a_n$. Each fence goes from $(a_i,0)$ to $(a_i,B)$. FJ also builds $m$ horizontal fences at $m$ distinct positions $b_1,\ldots,b_m$. Each fence goes from $(0,b_i)$ to $(A,b_i)$. The vertical and horizontal fences intersect each other, splitting the entire pasture into $(n+1)(m+1)$ regions. Unfortunately, FJ forgot to put gates in the fences, so each cow is trapped in a small region. He wants to fix this by removing some fences. Each time, he can choose two adjacent regions and remove the fence segment separating them. FJ's goal is to make it possible for the cows to reach any place in the pasture. Here is an example: ```plain +---+--+ | | | +---+--+ | | | | | | +---+--+ ``` After removing some fences, it becomes: ```plain +---+--+ | | +---+ + | | | | +---+--+ ``` To reduce the amount of work, FJ of course wants the total length of removed fences to be as small as possible.

The first line contains four integers $A, B, n, m$. It is guaranteed that $1 \leq n, m \leq 2000$ and $1 \leq A, B \leq 10^9$. The next $n$ lines each contain an integer $a_i$, with $0 < a_i < A$. The next $m$ lines each contain an integer $b_i$, with $0 < b_i < B$.

Output the minimum total length of fences to remove. **The answer must be stored in a 64-bit signed integer.**

Translated by ChatGPT 5