Optimális út

Adott egy magassági térkép, melyet n sorra és m oszlopra osztottunk fel. Az így kapott n*m cella mindegyikéhez hozzárendeltük a cella által reprezentált terület magasságát, mit nemnegatív egészt. Célunk, hogy a bal felső sarokból a jobb alsó sarokba jussunk négy szomszédos mezőkön végiglépkedve. (Egy mező négy szomszédja a felette, alatta, vagy mellette található legfeljebb 4 mező.) A szomszédos mezőre lépés költsége 10 egység, továbbá ehhez hozzá kell számolni a mezők magasságkülönbségét ha a szomszédos mező alacsonyabban van, illetve a magasságkülönbség dupláját, ha a szomszédos mező magasabban van.

Feladat

Határozza meg az optimális út költségét! A bemenet n sorban soronként m nem negatív egészt tartalmaz, melyeket egy-egy szóköz választ el egymástól. A kimenet egyetlen egész, az optimális út költsége legyen.

Példa bemenet:

1. 1 1 1
2. 1 1 1
3. 1 1 5

A példa bemenethez tartozó kimenet:

1. 48