Контрольный список коров
Каждый день Фермер Джон прогуливается по своему пастбищу проверить состояние всех своих коров. У него на ферме есть коровы двух пород: Holsteins и Guernseys. h коров породы Holsteins последовательно пронумерованы 1 .. h, и g Guernseys последовательно пронумерованы 1 .. g. Каждая из его коров расположена в точке на плоскости (точки не обязательно различны).
ФД начинает свою прогулку в позиции Holstein 1 а заканчивает в позиции Holstein h. Он хочет посетить каждую корову и для удобства ведёт чек-лист посещения коров. Он хочет посещать Holsteins и Guernseys в порядке их нумерации. В последовательности всех h + g коров, в порядке их посещения, коровы породы Holsteins 1 .. h появятся как подпоследовательности (не обязательно непрерывные), аналогично и с коровами породы Guernseys. Другими словами, последовательность всех h + g коров будет сформирована перемешиванием списка Holsteins пронумерованных 1 .. h и списка Guernseys, пронумерованных 1 .. g.
Когда ФД двигается от одной коровы к другой, преодолевая расстояние d, он тратит d^2 энергии. Помогите ему определить, минимальное количество энергии, требуемое чтобы посетить всех его коров в соответствии с правилами, описанными выше.
Входные данные
Первая строка ввода содержит h и g (1 ≤ h ≤ 1000, 1 ≤ g ≤ 1000). Последующие h строк содержат x и y координаты h Holsteins, и следующие g строк содержат координаты Guernseys. Каждая координата это целое число в интервале 0 .. 1000.
Выходные данные
Выведите одну строку, содержащую минимальную энергию, требуемую для посещения ФД всех его коров.