"Bugs Integrated" ir liela datoratmiņas ražotājfirma. Pašreiz tiek sagatavota sešu terabaitu atmiņas moduļu ražošana.

Katrs modulis sastāv no sešiem kvadrātiem, kas izvietoti taisnstūrī 2*3 vienības. Atmiņas moduļu ražošanas sākumfāzē no lielām silīcija plāksnēm tiek izgrieztas N*M vienības lielas plāksnes. Tās tiek rūpīgi pārbaudītas uz slikto kvadrātu klātbūtni un katrs sliktais kvadrāts tiek aizkrāsots ar melnu marķieri.

Visbeidzot, no šīs lielās silīcija plāksnes tiek izgrieztas atmiņas moduļu sagataves, katra no kurām sastāv no 2*3 (vai 3*2) vienības kvadrātiem. Saprotams, ka neviena no šīm sagatavēm nedrīkst saturēt nevienu no sliktajiem (aizkrāsotajiem) kvadrātiem. Iespējams, ka lielo plāksni nebūs iespējams sagriezt tā, lai visi labie kvadrāti būtu izmantoti kādā no atmiņas moduļu sagatavēm. Tomēr firma vēlētos izmantot pēc iespējas vairāk labos kvadrātus un noteikt, kādu lielāko atmiņas moduļu sagatavju skaitu iespējams izgriezt no attiecīgās plāksnes.

Ievaddatu pirmā rinda satur naturālu skaitli D(1<=D<=5) - pārbaudāmo silīcija plākšņu skaitu. Tālāk seko D datu bloki, katrs no kuriem apraksta vienu silīcija plāksni. Katra bloka pirmā rinda satur trīs veselus skaitļus N (1<=N<=150), M(1<=M<=10) un K(0<=K<=MN), kur N ir plāksnes platums, M ir plāksnes augstums un K ir slikto kvadrātu skaits plāksnē. Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols. Nākošajās K bloka rindās dots plāksnes slikto kvadrātu apraksts - pa vienam kvadrātam rindā. Katrā rindā doti divi naturāli skaitļi x un y (1<=x<=N,1<=y<=M), kas apzīmē sliktā kvadrāta kolonnas un rindas koordinātas (augšējā kreisā plāksnes kvadrāta koordinātas ir [1;1], bet apakšējā labējā stūra koordinātas ir [N;M]).

Izvaddatiem jāsatur tieši D rindas. Katrā rindā jāizvada viens vesels skaitlis. Faila i-tajā rindā jāizvada lielākais atmiņas sagatavju skaits kādu iespējams izgriezt no i-tajā datu blokā aprakstītās silīcija plāksnes.

Zīmējums pirmajam piemēra testam:

Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 2002.gadā.
Autors: Michal Forišek