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
Scrieti un program care sa determine efortul minim necesar pentru a lua pachetele
din dulap.
Date de intrare
Fisierul de intrare raft.in
contine:
raft.in
Semnificatie
C R
N
col1 lin1
col2 lin2
...
colN linN
C - numarul de coloane,
R - numarul de linii N - numarul de pachete
coli lini - pozitia pachetului i
Date de iesire
Fisierul de iesire raft.out
contine pe prima linie efortul minim determinat.
Restrictii
1 < = C <= 100, 1 <= R <= 100;
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
raft.in
raft.out
6 20
4
5 6
1 1
6 1
3 7
9
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi