Складена карта
Сад Фредді настільки розрісся, що йому знадобилася карта, щоб відобразити, які овочі і в яких ділянках посаджені. Він замовив високоякісну карту від Міжнародної картографічної компанії. Оскільки карта має великий масштаб, вона не вміщується на одній сторінці, тому її потрібно розділити на кілька прямокутних частин.
Навіть при фіксованому розмірі частини (визначається розміром сторінки) і масштабі карти, кількість частин може змінюватися в залежності від розташування сітки. Ваше завдання — знайти мінімальну кількість частин карти, необхідних для покриття всієї площі саду Фредді.
На зображенні показано два з багатьох варіантів розташування регіону Техас:
Розглянемо приклад. Ліворуч показано 14 частин карти, що покривають регіон. Але якщо трохи змістити положення карти, той самий регіон можна покрити всього 10 частинами, не змінюючи їх розмір і орієнтацію.
Усі частини карти повинні належати прямокутній сітці, паралельній осям x і y. Тобто вони можуть торкатися одна одної лише повністю сторонами і не можуть обертатися.
Вхідні дані
Складаються з кількох тестів. Перший рядок кожного тесту містить чотири цілі числа: A[r], A[c], T[r] і T[c]. A[r] і A[c] задають роздільну здатність вхідного зображення в пікселях (1 ≤ A[x] ≤ 1000), T[r] і T[c] - розмір однієї частини карти в пікселях (1 ≤ T[x] ≤ 100). Кожен з наступних A[r] рядків містить A[c] символів, кожен з яких або "X" (піксель відповідає частині саду, яку слід накрити частиною карти) або "." (піксель поза садом, який накривати не слід). Точки регіону формують одну зв'язну область.
Вихідні дані
Для кожного тесту вивести в окремому рядку найменшу кількість частин карти, якими можна накрити всі пікселі типу "X".