მერია

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, რეგიონული, X კლასი


ქალაქის მერიის შენობას მისი სიძველის გამო ერთ-ერთი კედელი დაუზიანდა. მერიის კედლები მოპირკეთებულია ერთეულოვანი სიგრძის გვერდის მქონე კვადრატული ფილებით. დაზიანებული კედლის კოდირებული გამოსახულება წარმოადგენს 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 დაკოპირება