Fenced In

题目描述

农夫约翰发现他的许多奶牛有一种奇怪的广场恐惧症（害怕大片开阔空间）。为了让它们不那么害怕放牧，他通过建造竖直（南北向）和水平（东西向）的栅栏，将大牧场划分为若干较小的区域。 大牧场是一个矩形，顶点为 $(0,0)$ 和 $(A,B)$。FJ 建造了 $n$ 道竖直栅栏（$0 \leq n \leq 2000$），位置分别为互不相同的 $a_1 \ldots a_n$（$0 < a_i < A$）；每道栅栏从 $(a_i, 0)$ 延伸到 $(a_i, B)$。 他还建造了 $m$ 道水平栅栏（$0 \leq m \leq 2000$），位置为 $b_1 \ldots b_m$（$0 < b_i < B$）；每道栅栏从 $(0, b_i)$ 延伸到 $(A, b_i)$。每道竖直栅栏都会与每道水平栅栏相交，从而将大牧场划分为总计 $(n+1)(m+1)$ 个区域。 不幸的是，FJ 完全忘了在栅栏上修建大门，使得奶牛无法离开其所在区域，在整个牧场中自由移动！他想通过移除部分栅栏来让奶牛能够在相邻区域之间通行。他希望选取若干对相邻区域，并移除分隔它们的整段栅栏；之后，他希望奶牛能通过这些开口在整个大牧场中到处走动。 例如，FJ 可能有如下的栅栏布局： +---+--+ | | | +---+--+ | | |
| | | +---+--+ 然后把它打开成这样： +---+--+ | |
+---+ +
| |
| | +---+--+ 请帮助 FJ 确定为实现目标他必须移除的栅栏总长度的最小值。

输入格式

第一行输入包含 $A$, $B$, $n$, 和 $m$（$1 \leq A, B \leq 1,000,000,000$）。接下来的 $n$ 行包含 $a_1 \ldots a_n$，再之后的 $m$ 行包含 $b_1 \ldots b_m$。

输出格式

请输出 FJ 必须移除的栅栏最小长度。注意该值可能大到无法放入标准 32 位整数，因此你可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

15 15 5 2
2
5
10
6
4
11
3

44

提示

题目来源：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold