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.
Teksta faila muris.in 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.
Teksta failā muris.out 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.
| muris.in | muris.out |
5 10 1110000111 1100001111 1000000011 1111101111 1110000111 |
1 7 2 1 3 2 5 1 |