1444: 建造栅栏

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:8 通过:3

题目描述

   农夫约翰的奶牛非常害怕在广阔的草地上吃草,为了避免他们的恐惧心理,约翰决定建造一些新的栅栏将草地分开。

   原来的草地是一个矩形,左下角是(0,0),右上角是(AB),约翰将要建造n个不同的垂直栅栏ai,每个栅栏的位置都是从(ai0)到(aiB),0<ai<A,他同时也要建造m不同的垂直栅栏bi0<bi<B,每个水平栅栏的位置都是从(0bi)到(Abi)。这些水平的栅栏和垂直的栅栏将整个草地分成了(n+1)*(m+1)个小矩形。

   约翰在建造栅栏的时候忘记造门了,这样就使得每个小矩形之间不能互通了。于是,他决定改变这个状况,他决定将一些相邻小矩形之间的栅栏完全去掉,使得相邻的小矩形能够联通。最终,他要使得所有的小矩形都能相互到达。例如,原来栅栏的建造方法如下:

删除了一些门之后,就变成了:

现在,请你求出最小去掉的栅栏的总长度,使得每个小矩形可以通过某些路径相互走到。

输入格式

     输入文件第一行是4个正整数ABnmAB表示原来草地的大小,nm表示建造的垂直栅栏和水平栅栏的数量。接下n行,每行一个整数ai,接下来m行,每行一个整数bi

输出格式

输出文件只有一行一个整数,表示去掉的栅栏的最小总长度。

输入样例 复制

15 15 5 2
2
5
10
6
4
11
3

输出样例 复制

44

数据范围与提示

【输入输出样例1说明】

自己算,大数据的输出结果可能需要int64

【数据说明】

0<=n<=2000,0<=m<=2000,1<=A,B<=1000000000