9M3 | pentagon

În urma bombardamentelor din $11$ septembrie $2001$, clădirea Pentagonului a suferit daune la unul din pereţii clădirii. Imaginea codificată a peretelui avariat se reprezintă sub forma unei matrice cu $m$ linii şi $n$ coloane, ca în figura de mai jos:

$1110000111 \\ 1100001111 \\ 1000000011 \\ 1000000011 \\ 1110000111 \\$

unde $1$ reprezintă zid intact și $0$ reprezintă zid avariat

Sumele alocate de Bin Laden pentru refacerea Pentagonului vor fi donate celor care vor ajuta americanii să refacă această clădire prin plasarea, pe verticală, a unor blocuri de înălţimi $k$, $k = 1, \ldots, m$, şi lăţime $1$, în locurile avariate.

Cerință

Pentru o structură dată a unui perete din clădirea Pentagonului, determinaţi numărul minim al blocurilor, de înălţimi $k=1, k=2, \ldots, k=m$, necesare refacerii clădirii.

Date de intrare

Fişierul de intrare pentagon.in conţine pe prima linie dimensiunile $m$ şi $n$ ale peretelui clădirii, iar pe următoarele $m$ linii câte o secvenţă de caractere $1$ sau $0$ de lungime $n$.

Date de ieșire

Fişierul pentagon.out va conţine pe câte o linie, ordonate crescător după $k$, secvenţe:

• $k$, $nr$ - unde $k$ este înalţimea blocului, iar $nr$ este numărul de blocuri de înălţime $k$, separate prin câte un spaţiu.

Restricții și precizări

• $1 < m,n \leq 200$
• nu se vor afişa blocurile de înălţime $k$, a căror număr este zero ($0$).

Exemplu

pentagon.in

5 10
1110000111
1100001111
1000000011
1111101111
1110000111

pentagon.out

1 7
2 1
3 2
5 1