Milli Xəzinələr
Milli muzeyin böyük zalı son vaxtlar bir neçə dəfə qarət olunub və bu, nümayiş olunan xəzinələrin təhlükəsizliyi ilə bağlı narahatlıqlara səbəb olub. Zalı qorumaq üçün muzey xüsusi mühafizə şirkəti ilə müqavilə bağlayıb ki, böyük zalda əlavə mühafizəçilər yerləşdirilsin və qədim əsərlərə nəzarət edilsin. Muzey, böyük zalın təhlükəsizliyini təmin etmək üçün mümkün olan ən az sayda əlavə mühafizəçi işə götürmək istəyir.
Böyük zal RxC ölçülü hüceyrələrdən ibarət iki ölçülü şəbəkə kimi təqdim olunur. Bəzi hüceyrələr artıq muzeyin mühafizəçiləri ilə doludur. Qalan bütün hüceyrələr müxtəlif növ əsərlərlə (heykəllər, heykəltəraşlıq əsərləri və s.) doludur ki, bunlar yeni işə götürülən mühafizəçilərlə əvəz edilə bilər. Hər bir əsər üçün zalda bir neçə digər hüceyrə əsərin kritik nöqtələri kimi müəyyən edilir, bu da əsərin dəyəri, saxlandığı seyfin növü və bir neçə digər amillərdən asılıdır. Başqa sözlə, əgər bu əsər zalda qalacaqsa, onda onun bütün kritik nöqtələrində mühafizəçilər dayanmalıdır. Bir neçə əsərin kritik mövqeyində dayanan mühafizəçi onların hamısına nəzarət edə bilər. Lakin mühafizəçi əsərin yerləşdiyi hüceyrədə dayana bilməz (əvəzində, mühafizəçinin orada dayanmasına imkan vermək üçün əsəri çıxara bilərsiniz). Həmçinin əsəri çıxarıb yeri boş buraxa bilməzsiniz (əsəri yalnız yeni işə götürülən mühafizəçi ilə əvəz edə bilərsiniz).
Böyük zalda bütün əsərləri araşdıraraq müəyyən etdiniz ki, hər hansı bir əsərin kritik nöqtələri (ilə işarələnmiş) aşağıdakı şəbəkədə göstərildiyi kimi həmişə 12 qonşu hüceyrənin alt çoxluğudur.
Buna uyğun olaraq, əsərin növü qeyri-mənfi tam ədəd kimi təyin edilə bilər, burada i-ci bit yalnız o zaman 1 olur ki, yuxarıdakı şəkildəki i nömrəli kritik nöqtə həmin əsərin kritik nöqtəsi olsun. Məsələn, 595 növündəki bir əsər (ikilikdə 1001010011) aşağıdakı şəkildə göstərildiyi kimi təsvir edilə bilər. Qeyd edək ki, bitlər sağdan sola nömrələnir (ən sağdakı bit 1 nömrəli bitdir). Əgər əsərin kritik nöqtəsi zalın şəbəkəsindən kənarda yerləşirsə, o, təhlükəsiz hesab olunur.
Sizə böyük zalın planı verilir və sizdən qalan əsərlərin hamısının təhlükəsizliyini təmin etmək üçün işə götürüləcək minimum sayda əlavə mühafizəçiləri tapmağınız xahiş olunur.
Giriş verilənləri
Proqramınız bir və ya bir neçə test halında sınaqdan keçiriləcək. Hər bir test halı R+1 sətirdən istifadə etməklə müəyyən edilir. Birinci sətir muzey zalının ölçüləri olan iki tam ədədi (1 ≤ R, C ≤ 50) göstərir. Növbəti R sətir bir və ya daha çox boşluqla ayrılmış C tam ədəd ehtiva edir. i-ci sətirin j-ci tam ədədi (i, j) hüceyrəsinin artıq muzeyin mühafizəçilərindən birini ehtiva edirsə -1, əks halda həmin hüceyrədəki əsərin növünü göstərən bir tam ədəd (0 ≤ T < 2^12) ehtiva edir.
Giriş faylının son sətirində iki sıfır var.
Çıxış verilənləri
Hər bir test halı üçün aşağıdakı sətiri çap edin: k. G
Burada k test halının nömrəsidir (birincidən başlayaraq) və G qalan əsərlərin təhlükəsizliyini təmin etmək üçün işə götürüləcək minimum sayda əlavə mühafizəçilərin sayıdır.
Sağdakı şəkil ikinci test halının həllini göstərir, burada ortadakı iki əsər mühafizəçilərlə əvəz olunub.