Nosaukums
Mūra siena (muris)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Kādas senas celtnes mūra sienā gadu gaitā ir izveidojies caurums. Kodētā veidā to apraksta matrica no m rindām un n kolonnām, kur 1 apzīmē, ka šajā vietā siena ir saglabājusies, bet 0 - ka nav (mūrī ir caurums).

Piemēram (m=5, n=10):

1110000111
1100001111
1000000011
1111101111
1110000111

Sienā esošo caurumu aiztaisīšanai var izmantot dažāda augstuma blokus, kuru platums ir viena, bet augstums - k vienības, 1<=k<=m.
Uzrakstiet programmu, kas dotam sienas aprakstam nosaka, kāds mazākais skaits kāda augstuma bloku nepieciešams, lai aizmūrētu visus sienā esošos caurumus.


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur divu naturālu skaitļu m (sienas augstums) un n (sienas platums) vērtības, kas atdalītas ar tukšumsimbolu. Zināms, ka 1<=m,n<=200.
Nākošajās m faila rindās ir dots sienas apraksts. Katrā rindā ir tieši n simboli (0 vai 1) bez atdalošajiem tukšumsimboliem.


Izvaddatu raksturojums

Izvaddatos jāizvada sienas aiztaisīšanai nepieciešamo bloku skaits to augstumu pieaugšanas secībā. Informācija par attiecīgā augstuma blokiem jāizvada tikai tad, ja šī augstuma bloki ir nepieciešami.Katrai faila rindai jāsatur divi naturāli skaitļi ki un pi, kas atdalīti ar tukšumsimbolu. ki ir attiecīgā garuma bloka augsums un pi - nepieciešamais šī augstuma bloku skaits.


Piezīmes

Uzdevums izmantots Rumānijas informātikas olimpiādē 2002.gadā.


Paraugdati

Stdin
5 10
1110000111
1100001111
1000000011
1111101111
1110000111
Stdout
1 7
2 1
3 2
5 1

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