Задача: Fenced In
Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a
1…a
n (0<a
i<A); каждая изгородь проходит от точки (a
i,0) до точки (a
i,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<b
i<B); каждая изгородь, проходит из (0,b
i) в (A,b
i). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
Например, ФД мог построить изгороди так:
+---+--+
| | |
+---+--+
| | |
| | |
+---+--+
и открыть их так:
+---+--+
| |
+---+ +
| |
| |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
ФОРМАТ ВВОДА:
Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a1…an. Следующие m строк содержат b1…bm.
ФОРМАТ ВЫВОДА:
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
| Ввод |
Вывод |
|
15 15 5 2
2
5
10
6
4
11
3
|
44 |
Ваш ответ: