Національні скарби
Велика зала національного музею нещодавно кілька разів зазнала пограбувань. Тепер усі стурбовані безпекою скарбів, що виставлені на показ. Щоб допомогти забезпечити безпеку зали, музей уклав контракт із приватною охоронною компанією для надання додаткових охоронців, які залишатимуться у великій залі та стежитимуть за стародавніми артефактами. Музей прагне найняти мінімальну кількість додаткових охоронців, щоб велика зала була захищена.
Велика зала представлена у вигляді двовимірної сітки розміром RxC. Деякі клітинки вже зайняті охоронцями музею. Усі інші клітинки зайняті артефактами різних типів (статуї, скульптури тощо), які можуть бути замінені новими найнятими охоронцями. Для кожного артефакту кілька інших клітинок у залі визначені як критичні точки артефакту залежно від його цінності, типу сховища, в якому він зберігається, та кількох інших факторів. Іншими словами, якщо цей артефакт залишиться в залі, то всі його критичні точки повинні бути під охороною. Охоронець, що стоїть у критичній точці кількох артефактів, може стежити за ними всіма. Однак охоронець не може стояти в клітинці, яка містить артефакт (замість цього, ви можете видалити артефакт, щоб дозволити охоронцю залишитися там). Також ви не можете видалити артефакт і залишити місце вільним (ви можете лише замінити артефакт новим найнятим охоронцем).
Оглядаючи всі артефакти у великій залі, ви з'ясували, що критичні точки будь-якого артефакту (позначені ) завжди є підмножиною 12 сусідніх клітинок, як показано на сітці нижче.
Відповідно, тип артефакту може бути вказаний як невід'ємне ціле число, де i-й біт дорівнює 1, лише якщо критична точка номер i з малюнка вище є критичною точкою цього артефакту. Наприклад, артефакт типу 595 (у двійковій системі 1001010011) можна зобразити, як показано на малюнку нижче. Зверніть увагу, що біти нумеруються з права наліво (правий біт є бітом номер 1). Якщо критична точка артефакту знаходиться за межами сітки зали, то вона вважається захищеною.
Вам надано план великої зали і потрібно знайти мінімальну кількість додаткових охоронців, щоб усі залишені артефакти були захищені.
Вхідні дані
Ваша програма буде протестована на одному або кількох тестових випадках. Кожен тестовий випадок задається за допомогою R+1 рядків. Перший рядок задає два цілі числа (1 ≤ R, C ≤ 50), які є розмірами зали музею. Наступні R рядків містять C цілих чисел, розділених одним або кількома пробілами. j-е ціле число i-го рядка дорівнює -1, якщо клітинка (i, j) вже містить одного з охоронців музею, інакше вона містить ціле число (0 ≤ T < 2^12), що представляє тип артефакту в цій клітинці.
Останній рядок вхідного файлу містить два нулі.
Вихідні дані
Для кожного тестового випадку виведіть наступний рядок: k. G
Де k — номер тестового випадку (починаючи з одного), а G — мінімальна кількість додаткових охоронців, яких потрібно найняти, щоб усі залишені артефакти були захищені.
На малюнку праворуч показано рішення другого тестового випадку, де два артефакти посередині замінені охоронцями.