За забором (Золото)
Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.Поле представляет собой прямоугольник с угловыми вершинами в точках (0, 0) и (a, b). ФД построил n вертикальных изгородей в различных позициях a[1]
... a[n]
(0 < a[i]
< a), каждая изгородь проходит от точки (a[i]
, 0) до точки (a[i]
, b). Он также построил m горизонтальных изгородей в в различных позициях b[1]
... b[m]
(0 < b[i]
< b); каждая изгородь, проходит из (0, b[i]
) в (a, b[i]
). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n + 1) (m + 1) регионов.
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
Например, ФД мог построить изгороди так:
+---+--+ | | | +---+--+ | | | | | | +---+--+
и открыть их так:
+---+--+ | | +---+ + | | | | +---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
Входные данные
Первая строка содержит числа a, b (1 ≤ a, b ≤ 10^9
), n (0 ≤ n ≤ 2000) и m (0 ≤ m ≤ 2000). Следующие n строк содержат a[1]
... a[n]
. Следующие m строк содержат b[1]
... b[m]
.
Выходные данные
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое.