8410: BZOJ4410:[Usaco2016 Feb]Fence in

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

有一个平面,左下角是(0,0),右上角是(A,B)。 有n个平行于y轴的栅栏a1..an,表示挡在(ai,0)到(ai,B)之间。 有m个平行于x轴的栅栏b1..bn,表示挡在(0,bi)到(A,bi)之间。 这样,平面被划成了(n+1)*(m+1)块。 现在要去掉某些栅栏的一部分,使得每一块都连通。 比如原来是这样:

可以去掉后变成这样:

求最少需要去掉多少长度的栅栏使得每一块都连通。


输入格式

第一行四个数A,B,n,m。 A<=1000000000 ,B<=1000000000 N<=25000 M<=25000 接下来n行每行一个数表示ai 接下来m行每行一个数表示bi。 0<ai<A  0<bi<B 


输出格式

输出一个数表示答案。


样例输入

15 15 5 2
2
5
10
6
4
11
3

样例输出

44

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: