Nosaukums
Arhīva plaukti (plaukti)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Arhīva dokumenti glabājas plauktos, kas izvietoti viens otram blakus rindās un kolonnās viens virs otra.

Lai paņemtu kādu dokumentu, nepieciešams izmantot kāpnītes, kas tiek pieslietas kādai plauktu kolonnai. Uzrāpjoties pa kāpnītēm līdz kādam augstumam (plauktu rindai R), ir iespējams aizsniegt jebkuru plauktu šajā kolonnā, kas atrodas ne augstāk par rindu R, kā arī plauktus šajā pat augstumā blakus kolonnās pa labi un pa kreisi.

Arhivāram nepieciešams dabūt dokumentus no noteiktiem plauktiem. Lai samazinātu krišanas un savainošanās draudus, kopējam kāpšanas augstumam (atsevišķu kāpienu augstumu summai) vajadzētu būt pēc iespējas mazākam.

Uzrakstiet programmu, kas nosaka mazāko kopīgo kāpšanas augstumu!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu C(plauktu kolonnu skaits,1≤C≤100) un R(plauktu rindu skaits, 1≤R≤100) vērtības, kas atdalītas ar tukšumsimbolu.

Faila otrajā rindā dota naturāla skaitļa N(aizsniedzamo plauktu skaits,1≤N≤100) vērtība.

Katrā no nākošajām N rindām katrā dots pa diviem naturāliem skaitļiem A un B, 1≤A≤C,1 ≤B≤R, kas atdalīti ar tukšumsimbolu. A ir aizsniedzamā plaukta kolonnas, bet B - rindas numurs.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada naturāls skaitlis - mazākais kopīgais kāpšanas augstums.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā


Paraugdati

Stdin
5 5
3
2 3
3 4
4 4
Stdout
4

Stdin
6 20
4
5 6
1 1
6 1
3 7
Stdout
9

Stdin
10 10
5
9 1
7 6
5 8
4 1
3 2
Stdout
11

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.