Autoput1

Zamislimo pojednostavljeni autoput u koordinatnom sustavu. Cesta ide slijeva na desno, prati konfiguraciju terena i prilikom prelaska svakog jediničnog kvadratića može:
a) ostati na istoj visini
b) spustiti se ili popeti se za jedan kvadratić
Automobil vozi po cesti slijeva na desno, a vrijeme potrebno da prijeđe jedan kvadratić iznosi A sekundi za slučaj a), a B sekundi za slučaj b).Međutim, mi ispod nekih planina ili iznad nekih ponora možemo prokopati tunel odnosno izgraditi vijadukt. Oni moraju biti vodoravni, a vrijeme potrebno da automobil prijeđe jedan kvadratić kroz tunel odnosno preko vijadukta iznosi [] sekundi.Napišite program koji će za zadanu konfiguraciju terena izračunati minimalno vrijeme potrebno da automobil prijeđe cijeli autoput uz optimalnu izgradnju tunela i vijadukata. Pri tome ukupan broj izgrađenih tunela i vijadukata ne smije biti veći od K.