Контрольний список корів

Кожного дня фермер Джон обходить своє пасовище, щоб перевірити стан кожної зі своїх корів. На його фермі є дві породи корів: Holstein та Guernsey. Його $h$ корів Holstein пронумеровані $\mathrm{1..}h$, а $g$ корів Guernsey — $\mathrm{1..}g$. Кожна корова знаходиться в певній точці двовимірної площини (координати різних корів не обов'язково різняться).

Фермер Джон починає свій маршрут біля корови Holstein $1$ і закінчує його біля корови Holstein $h$. По дорозі він хоче відвідати кожну корову. Щоб йому було зручніше вести список уже відвіданих корів, він хоче відвідувати корів Holstein та Guernsey в порядку їхніх номерів. У послідовності з усіх h + g відвіданих корів корови Holstein з номерами $\mathrm{1..}h$ повинні зустрічатися як підпослідовність (не обов'язково неперервна), і те саме повинно виконуватися для корів Guernsey. Іншими словами, послідовність усіх h + g корів повинна бути отримана шляхом злиття списку корів Holstein з номерами $\mathrm{1..}h$ і списку корів Guernsey з номерами $\mathrm{1..}g$, при цьому порядок всередині кожного списку повинен зберігатися.

Коли ФД переміщується від однієї корови до іншої на відстань $d$, він витрачає d^2 одиниць енергії. Допоможіть йому визначити мінімальну кількість енергії, необхідну для відвідування всіх його корів згідно з описаними правилами.