Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле
на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках \((0,0)\) and \((A,B)\). ФД построил \(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)\) регионов.
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
Например, ФД мог построить изгороди так:
+---+--+
| | |
+---+--+
| | |
| | |
+---+--+
и открыть их так:
+---+--+
| |
+---+ +
| |
| |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
ФОРМАТ ВВОДА (файл fencedin.in):
Первая строка ввода содержит числа \(A\), \(B\), \(n\), and \(m\)
(\(1 \leq A, B \leq 1,000,000,000\)). Следующие \(n\) строк содержат \(a_1 \ldots a_n\).
Следующие \(m\) строк содержат \(b_1 \ldots b_m\).
ФОРМАТ ВЫВОДА (файл fencedin.out):
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
Примеры
| № | Входные данные | Выходные данные |
|
1
|
15 15 5 2
2
5
10
6
4
11
3
|
44
|