ნათურები

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

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

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

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

წყარო: GEOI, 2010, დასკვნითი, IX კლასამდე


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



მაგალითები

შესატანი მონაცემები
5 6 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 დაკოპირება
გამოსატანი მონაცემები
5 დაკოპირება

შენიშვნა

განმარტება: მოცემული კონფიგურაციის მიღება შესაძლებელია მე-2 და მე-5 სვეტების და 1-ლი, მე-2 და მე-3 სტრიქონების ჩართვით. ანუ, მინიმალური ჯამური რაოდენობა 5-ის ტოლია.