Каждый день Фермер Джон прогуливается по своему пастбищу проверить состояние
всех своих коров. У него на ферме есть коровы двух пород: Holsteins и Guernseys.
\(H\) коров породы Holsteins последовательно пронумерованы \(1 \ldots H\), и
\(G\) Guernseys последовательно пронумерованы \(1 \ldots G\) ($1 \leq H \leq 1000,
1 \leq G \leq 1000$). Каждая из его коров расположена в точке на плоскости
(точки не обязательно различны).
ФД начинает свою прогулку в позиции Holstein 1 а заканчивает в позиции
Holstein \(H\). Он хочет посетить каждую корову и для удобства ведёт чек-лист
посещения коров. Он хочет посещать Holsteins и Guernseys в порядке их
нумерации. В последовательности всех \(H+G\) коров, в порядке их посещения,
коровы породы Holsteins \(1 \ldots H\) появятся как подпоследовательности
(не обязательно непрерывные), аналогично и с коровами породы Guernseys.
Другими словами, последовательность всех \(H+G\) коров будет сформирована
перемешиванием списка Holsteins пронумерованных \(1 \ldots H\) и списка
Guernseys, пронумерованных \(1 \ldots G\).
Когда ФД двигается от одной коровы к другой, преодолевая расстояние \(D\),
он тратит \(D^2\) энергии. Помогите ему определить, минимальное количество
энергии, требуемое чтобы посетить всех его коров в соответствии с правилами,
описанными выше.
ФОРМАТ ВВОДА (файл checklist.in):
Первая строка ввода содержит
\(H\) и
\(G\), разделённые одиночным пробелом.
Последующие \(H\) строк содержат \(x\) и \(y\) координаты \(H\) Holsteins, и
следующие \(G\) строк содержат координаты Guernseys. Каждая координата
это целое число в интервале \(0 \ldots 1000\).
ФОРМАТ ВЫВОДА (файл checklist.out):
Выведите одну строку, содержащую минимальную энергию, требуемую для посещения ФД
всех его коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 0
1 0
2 0
0 3
1 3
|
20
|