Državno natjecanje iz informatike / Srednja škola Druga podskupina (3. i 4. razred) / Drugi dan natjecanja - 1. zadatak

Dva dugačka otoka pružaju se jedan uz drugi u smjeru sjever-jug.

Na lijevom otoku postoji M gradova označenih brojevima od 1 do M od sjevera prema jugu, a na desnom otoku postoji N gradova označenih brojevima od 1 do N od sjevera prema jugu.

Za bilo koji grad lijevog i bilo koji grad desnog otoka postoji izravna trajektna linija koja ih povezuje. Tih linija, dakle, ima M ⋅ N.

Svaka trajektna linija ima svoju cijenu vožnje.

Budući da stanovnici ovih otoka najviše koriste novčanice vrijednosti K novčanih jedinica, predsjednik ovih otoka odlučio je regulirati cijene tako da sve budu djeljive s K.

Ujedno želi i povećati cijene, pa je odlučio iskoristiti činjenicu da su stanovnici sjevernih gradova bogatiji i da njihove linije mogu više koštati.

Konkretno, predsjednik će više puta donijeti sljedeću odluku: odabrat će neku liniju A-B i potom cijenu te linije, kao i cijene svih linija sjeverno od linije A-B, povećati za proizvoljan isti iznos.

(Linija X-Y je sjeverno od linije A-B ako je X ≤ A i Y ≤ B.) Primjerice, ako predsjednik poveća cijenu linije 2- 3 za 10 novčanih jedinica, onda se isto povećanje događa za linije 1-1, 1-2, 1-3, 2-1 i 2-2.

Pomozite predsjedniku izračunati najmanji broj odluka koje on mora donijeti da bi cijene svih trajektnih linija postale djeljive s K. (Taj će cilj biti ostvariv u svim testnim primjerima.)

Ulazni podaci

U prvom su retku prirodni brojevi M i N (1 ≤ M, N ≤ 2000) iz teksta zadatka.

U drugom je retku prirodan broj K (2 ≤ K ≤ 100) iz teksta zadatka.

Slijedi najviše 100 000 redaka od kojih u svakom pišu tri prirodna broja A, B i C (1 ≤ A ≤ M, 1 ≤ B ≤ N, 1 ≤ C ≤ 1000) koji znače da početna cijena linije A-B iznosi C novčanih jedinica.

Svaka linija bit će navedena najviše jednom, a za linije koje nisu navedene početna cijena iznosi 0 novčanih jedinica.

Na kraju slijedi redak „0 0 0“ koji označava kraj ulaznih podataka.

Izlazni podaci

U jedini redak ispišite traženi najmanji broj odluka.

PRIMJERI TEST PODATAKA

Ulaz

2 3
10
1 3 16
0 0 0

Izlaz

2

Objašnjenje

Pojašnjenje prvog primjera: Na početku su sve linije besplatne osim linije 1-3 čija je cijena 16.

Želimo da sve cijene budu djeljive s deset. Povećamo cijenu linije 1-3 npr. za 4, nakon čega je njezina cijena 20, ali sada njoj sjeverne linije 1-1 i 1-2 dobivaju cijenu 4.

Novim povećanjem cijene linije 1-2, npr. za 6, cijena te linije postaje 10, kao i cijena linije 1-1.

Sada su sve cijene djeljive s deset. (Cijene linija iz lijevog grada 2 nismo mijenjali, tj. one su ostale 0 kuna, što je također djeljivo s deset.)

Ulaz

3 2
60
1 2 20
2 2 80
3 1 70
3 2 150
0 0 0

Izlaz

3

Objašnjenje

Pojašnjenje drugog primjera: Jedna je mogućnost donijeti sljedeće odluke: