Коні

Шаховий кінь — це фігура, яка рухається по шахівниці, перестрибуючи $2$ клітинки в одному з $4$ напрямків (вліво, вправо, вгору або вниз), а потім $1$ клітинку у перпендикулярному напрямку. Кажуть, що фігура контролює клітинку, якщо вона може досягти цієї клітинки за будь-яку кількість ходів. Дошка може мати нескінченну довжину та/або ширину, тобто містити нескінченну кількість клітинок. Наприклад, дошка розміру \textbf{INF} \times M — це смуга нескінченної довжини з шириною $M$, а дошка розміру \textbf{INF} \times \textbf{INF} — повністю нескінченна, без меж. Дано дошку розміром N \times M (1 \leq N, M \leq 1000) або нескінченності ($\text{INF}$). Визначте мінімальну кількість коней, потрібну, щоб контролювати всю дошку.