Lista di controllo delle vacche

Ogni giorno, il contadino John percorre il suo pascolo per controllare lo stato di ciascuna delle sue vacche. Nella sua fattoria ci sono due razze di vacche: Holstein e Guernsey. Le sue $h$ vacche Holstein sono numerate $\mathrm{1..}h$, e le $g$ vacche Guernsey $\mathrm{1..}g$. Ogni vacca si trova in un certo punto del piano bidimensionale (le coordinate di vacche diverse non sono necessariamente distinte).

Il contadino John inizia il suo percorso dalla vacca Holstein $1$ e lo termina alla vacca Holstein $h$. Lungo il percorso desidera visitare ogni vacca. Per rendergli più comodo tenere un elenco delle vacche già visitate, egli vuole visitare le vacche Holstein e Guernsey nell'ordine dei loro numeri. Nella sequenza di tutte le h + g vacche visitate, le vacche Holstein numerate $\mathrm{1..}h$ devono comparire come sottosequenza (non necessariamente continua), e lo stesso deve valere per le vacche Guernsey. In altre parole, la sequenza di tutte le h + g vacche deve essere ottenuta unendo la lista delle vacche Holstein numerate $\mathrm{1..}h$ con la lista delle vacche Guernsey numerate $\mathrm{1..}g$, mantenendo l'ordine all'interno di ciascuna lista.

Quando FJ si sposta da una vacca a un'altra a distanza $d$, egli consuma d^2 unità di energia. Aiutatelo a determinare la quantità minima di energia necessaria per visitare tutte le sue vacche secondo le regole descritte.