Скарб Капітана Q
Ви знайшли стару карту, створену відомим піратом "Капітаном Q". Вона показує місця, де на острові закопані скрині зі скарбами.
Карта розділена на квадратні секції, кожна з яких може містити цифру або бути порожньою. Цифра вказує на кількість скринь у 9 сусідніх секціях (включаючи саму секцію та її 8 сусідів). Ви можете припустити, що в кожній секції може бути не більше однієї скрині.
Хоча у вас є карта, ви не можете точно визначити, де закопані скрині. Навіть загальна кількість скринь на острові невідома. Однак, можна обчислити мінімальну кількість скринь, закопаних на острові. Ваше завдання - написати програму, яка обчислює цю кількість.
Вхідні дані
Вхідні дані складаються з кількох наборів. Кожен набір даних має такий формат:
h w
Перша строка набору даних містить два додатні цілі числа h та w. h - це висота карти, а w - це ширина карти. Ви можете припустити, що 1 ≤ h ≤ 15 та 1 ≤ w ≤ 15.
Наступні h рядків представляють карту. Кожен рядок складається з w символів і відповідає горизонтальній смузі карти. Кожен символ у рядку описує стан секції наступним чином:
'.': Секція не є частиною острова (вода). Тут немає скрині.
'*': Секція є частиною острова, і кількість скринь у її 9 сусідах невідома.
'0'-'9': Секція є частиною острова, і цифра вказує на кількість скринь у її 9 сусідах.
Ви можете припустити, що карта не суперечлива, тобто існує принаймні одне можливе розташування скринь. Також можна припустити, що кількість секцій з цифрами становить принаймні одну і не більше 15.
Рядок, що містить два нулі, вказує на кінець введення.
Вихідні дані
Для кожного набору даних виведіть рядок, що містить мінімальну кількість скринь. Вихід не повинен містити жодних інших символів.