eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Мінер

Мінер

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Кожен мінер знає, що ймовірність підірватись на міні дуже сильно залежить від того, наскільки професійно вони розставлені.

Широко відома гра "Мінер" проходить на прямокутному полі з w×h клітинок. У кожній клітинці або стоїть міна, або записано кількість мін, які розміщені у вісьми сусідніх клітинках (число від 0 до 8).

У цій задачі Вам необхідно взнати, яку мінімальну кількість мін знадобиться, щоб не виявилось жодної клітинки, у якій чи поруч з якою не буде міни.

Вхідні дані

У першому рядку вхідного файлу знаходяться два цілих числа w та h (1w, h1000), відокремлені пропуском - ширина та висота поля, відповідно.

Вихідні дані

У єдиному рядку вихідного файлу виведіть мінімальну кількість мін, достатню для того, щоб у кожній клітинці ігрового поля або стояла міна, або було записано число більше нуля.

Другий приклад (поле 5×5) проілюстровано на наступному малюнку:

Приклад

Вхідні дані #1
3 3
Вихідні дані #1
1
Джерело Blitz Contest by SPbETU & Michael Dvorkin, Petrozavodsk Winter Training Session, January 31, 2006