За забором (Платина)
За забором (Платина)
Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0, 0) и (a, b). ФД построил n вертикальных изгородей в различных позициях a1
... an
(0 < ai
< a); каждая изгородь проходит от точки (ai
, 0) до точки (ai
, b). Он также построил m горизонтальных изгородей в в различных позициях b1
... bm
(0 < bi
< b); каждая изгородь, проходит из (0, bi
) в (a, bi
). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n + 1) (m + 1) регионов.
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
Например, ФД мог построить изгороди так:
+---+--+
| | |
+---+--+
| | |
| | |
+---+--+
и открыть их так:
+---+--+
| |
+---+ +
| |
| |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
Входные данные
Первая строка содержит числа a, b (1 ≤ a, b ≤ 109
), n (0 ≤ n ≤ 25000) и m (0 ≤ m ≤ 25000). Следующие n строк содержат a1
... an
. Следующие m строк содержат b1
... bm
.
Выходные данные
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое.
15 15 5 2 2 5 10 6 4 11 3
44