You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题和 金组同名题目 在题意上一致，唯一的不同是数据范围。

题目描述

Farmer John 意识到他的奶牛最近患上了一种恐惧症（害怕过于开阔的空间）。为了减少放牧的恐惧，FJ 决定在牧场中建一些水平和竖直方向的栅栏来将牧场分成若干个小区域。

整个牧场是一个矩形，两个角的坐标分别为 $(0,0)$ 和 $(A,B)$。FJ 在 $a_1,\ldots ,a_n$ 这 $n$ 个两两不同的位置建造了竖直方向的栅栏，每个栅栏从 $(a_i,0)$ 到 $(a_i,B)$；FJ 在 $b_1,\ldots ,b_m$ 这 $m$ 个两两不同的位置建造了水平方向的栅栏，每个栅栏从 $(0,b_i)$ 到 $(A,b_i)$。竖直方向的栅栏和水平方向的栅栏两两相交，将整个牧场分割成 $(n+1)(m+1)$ 个区域。

不幸的是，FJ 忘记了在栅栏上开门，奶牛都只能被困在一个个的小区域里！他想通过去掉一些栅栏来解决这个问题。他一次可以选择两个相邻的区域，将隔离这两个区域的栅栏去掉。FJ 的目标是让奶牛能够抵达牧场的任意一个地方。

这是一个例子：

+---+--+
|   |  |
+---+--+
|   |  |
|   |  |
+---+--+

去掉一些栅栏后的效果是这样的：

+---+--+
|      |
+---+  +
|      |
|      |
+---+--+

为了降低工程量，FJ 当然希望拆除的栅栏长度最短。

输入格式

第一行四个整数 $A,B,n,m$，保证 $1 \leq n,m \leq 2.5 \times 10^5$，$1 \leq A,B \leq 10^9$。

接下来 $n$ 行，第 $i$ 行一个整数 $a_i$，保证 $0 \lt a_i \lt A$。

接下来 $m$ 行，第 $i$ 行一个整数 $b_i$，保证 $0 \lt b_i \lt B$。

输出格式

输出拆除栅栏的最小长度。答案需要用 64 位带符号整数存储。

15 15 5 2
2
5
10
6
4
11
3

44