Мінер#4875
Кожен мінер знає, що ймовірність підірватись на міні дуже сильно залежить від того, наскільки професійно вони розставлені.
Широко відома гра "Мінер" проходить на прямокутному полі з w \times h клітинок. У кожній клітинці або стоїть міна, або записано кількість мін, які розміщені у вісьми сусідніх клітинках (число від до ).
У цій задачі Вам необхідно дізнатися, яку мінімальну кількість мін знадобиться, щоб не виявилось жодної клітинки, у якій чи поруч з якою не буде міни.
У першому рядку вхідного файлу знаходяться два цілих числа та (1 \le w, h \le 1000), відокремлені пропуском - ширина та висота поля, відповідно.
У єдиному рядку вихідного файлу виведіть мінімальну кількість мін, достатню для того, щоб у кожній клітинці ігрового поля або стояла міна, або було записано число більше нуля.
Другий приклад (поле 5 \times 5) проілюстровано на наступному малюнку:
Приклад 1