raft

Lenuta lucreaza la un oficiu postal. Aici, pachetele sunt depozitate într-un dulap special. Dulapul are R rafturi, fiecare raft fiind împartit în C casute de dimensiuni egale. Prin urmare, putem considera ca dulapul este constituit din R linii si C coloane. Pentru a lua pachete din dulap se utilizeaza o scara mobila. Scara trebuie fixata în dreptul unei coloane. Urcând pe scara pâna la un anumit raft (linie), este posibil sa luam orice pachet pâna la înaltimea respectiva de pe coloana pe care este fixata scara, dar si de pe coloanele adiacente (cea din stânga si cea din dreapta).
La un moment dat, Lenuta trebuie sa ia din dulap anumite pachete si doreste sa realizeze acest lucru cu efort minim. Efortul depus pentru luarea tuturor pachetelor este egal cu suma înaltimilor pâna la care urca Lenuta pentru a lua toate pachetele.

Cerinta

Fisierul de intrare raft.in contine:

Date de iesire

Fisierul de iesire raft.out contine pe prima linie efortul minim determinat.

Restrictii

• C si R sunt numere naturale, 1< = C <= 100, 1 <= R <= 100;
• Numarul de pachete N este un numar natural 1 <= N <= 100;
• Liniile sunt numerotate de jos în sus de la 1 la R, iar coloanele sunt numerotate de la stânga la dreapta de la 1 la C.

Exemple

raft.in	raft.out
5 5 3 2 3 3 4 4 4	4