围栏拆除(Fenced In P)

题目描述

本题对应 USACO 2016 February Contest, Platinum Problem 2：Fenced In。

农夫约翰的牧场是一个左下角在 $(0, 0)$、右上角在 $(A, B)$ 的矩形区域。他修建了 $n$ 条竖直栅栏（位于横坐标 $a_1, a_2, \dots, a_n$，从 $(a_i, 0)$ 延伸到 $(a_i, B)$）和 $m$ 条水平栅栏（位于纵坐标 $b_1, b_2, \dots, b_m$，从 $(0, b_j)$ 延伸到 $(A, b_j)$）。

这些栅栏将整个牧场划分成了 $(n + 1)(m + 1)$ 个矩形小区域。为了让奶牛能够在任意两个小区域之间自由走动，农夫约翰需要拆除若干段相邻小区域之间的栅栏段（每段栅栏拆除的花费等于该段栅栏的长度）。

请你计算，使所有 $(n + 1)(m + 1)$ 个小区域全部连通所需拆除的栅栏总长度的最小值。

输入格式

第一行包含四个整数 $A, B, n, m$。

接下来 $n$ 行，每行一个正整数 $a_i$（$0 < a_i < A$），表示一条竖直栅栏的横坐标。

接下来 $m$ 行，每行一个正整数 $b_j$（$0 < b_j < B$），表示一条水平栅栏的纵坐标。

输出格式

输出一行一个整数，表示使所有区域连通所需拆除的最小栅栏总长度。

样例输入 #1

15 15 5 2
2
5
10
6
4
11
3

样例输出 #1

44

数据范围

对于 $100\%$ 的数据，$1 \le A, B \le 10^9$，$0 \le n, m \le 25000$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接