Розфарбовування
На планеті Олімпія щороку проводиться традиційна гра "Розмальовки". Місцем проведення цієї гри є велике олімпійське поле розміром N×M, де кожна клітинка пофарбована в білий або чорний колір. Двоє гравців ходять по черзі, здійснюючи загалом K ходів. Під час свого ходу гравець може зафарбувати власним кольором всі клітинки будь-якого одного прямокутника, висота і ширина якого не перевищують D. Перший гравець зафарбовує клітинки в білий колір, а другий — в чорний. Після завершення K-го ходу підраховується остаточний рахунок гри — кількість клітинок кожного кольору. Переможцем стає той гравець, у якого більше клітинок його кольору. Отже, мета кожного гравця — максимізувати кількість клітинок свого кольору в кінцевому розфарбуванні поля.
Напишіть програму, яка за початковим розфарбуванням, кількістю ходів і обмеженнями на розмір прямокутника, який може зафарбовувати гравець, визначить остаточний рахунок гри при оптимальній стратегії обох гравців.
Вхідні дані
Перша рядок містить чотири натуральних числа: N, M, D і K (N ≤ 400, M ≤ 400, D ≤ 400, K ≤ 10^9) — висота і ширина поля, обмеження на розмір прямокутника, який може зафарбовувати гравець, кількість ходів, які потрібно виконати до підведення остаточного рахунку. У наступних N рядках розташовано по M символів: W, якщо відповідна клітинка розфарбована в білий колір, і B, якщо клітинка розфарбована в чорний колір.
Вихідні дані
Єдиний рядок повинен містити два цілих числа — кількість білих і кількість чорних клітинок у кінцевому розфарбуванні при умові оптимальної гри обох гравців.