ქალაქის მერიის შენობას მისი სიძველის გამო ერთ-ერთი კედელი დაუზიანდა. მერიის კედლები მოპირკეთებულია ერთეულოვანი სიგრძის გვერდის მქონე კვადრატული ფილებით. დაზიანებული კედლის კოდირებული გამოსახულება წარმოადგენს 0-ებისა და 1-ებისაგან შედგენილ ცხრილს, რომელიც m რაოდენობის სტრიქონისა და n რაოდენობის სვეტისაგან შედგება.

ქვემოთ მოცემულია ამ კედლის გამოსახულების მაგალითი, სადაც 0-ებით დაზიანებული ფილებია გამოსახული, ხოლო 1-ებით კი – დაუზიანებელი ფილები:

1110000111

1100001111

1000000011

1111101111

1110000111

 ქალაქის მერიამ კედლის შეკეთებისათვის გამოაცხადა ტენდერი, სადაც ხარჯების მინიმიზაციის მიზნით ჩადებულია პირობა, რომ კედლის დაუზიანებელი უბნები ხელუხლებლად უნდა დარჩეს, ხოლო დაზიანებულ უბნებზე ვერტიკალურად უნდა განთავსდეს k (k=1,2,3,…,მ) სიმაღლის და ერთეულოვანი სიგანის ახალი ფილები.

დაწერეთ პროგრამა, რომელიც მერიის დაზიანებული კედლის მოცემული სტრუქტურისათვის იპოვის მის შესაკეთებლად საჭირო k (k=1,2,3,…,მ) სიმაღლის და ერთეულოვანი სიგანის ფილების მინიმალურ რაოდენობას.

შესატანი მონაცემები:  პირველ სტრიქონში მოცემულია ორი მთელი დადებითი  m და n  რიცხვი (1 ≤ m,n ≤ 200) – დაზიანებული კედლის განზომილებები. მომდევნო მ რაოდენობის სტრიქონი წარმოადგენს კედლის კოდირებულ გამოსახულებას. თითოეულ მათგანში ჩაწერილია n რაოდენობის სიმბოლო (0 ან 1).

გამოსატანი მონაცემები:  უნდა ჩაიწეროს კედლის შესაკეთებლად საჭირო ფილების აღწერა. მისი თითოეული  სტრიქონი უნდა შეიცავდეს ერთი ჰარით გამოყოფილ ორ მთელ k და p რიცხვს, სადაც კ ფილის სიმაღლეა, ხოლო p კი ამ სიმაღლის ფილების მინიმალური რაოდენობა. ფაილში ფილები დალაგებული უნდა იყოს მათი სიმაღლეთა ზრდის მიხედვით. გამოსატან მონაცემთა ფაილი არ უნდა შეიცავდეს k სიმაღლის ისეთ ფილებს, რომელთათვისაც p=0.

მაგალითები

შესატანი მონაცემები
5 10
1110000111 
1100001111
1000000011
1111101111
1110000111
                  დაკოპირება

გამოსატანი მონაცემები
1 7
2 1
3 2
5 1
                  დაკოპირება