Розфарбування#3039
На планеті Олімпія проходить традиційна щорічна гра "Розфарбування". Гра відбувається на великому полі розміром N \times M, де кожна клітинка спочатку пофарбована або в білий, або в чорний колір. Двоє гравців ходять по черзі, загалом здійснюючи рівно ходів. За один хід гравець може перефарбувати всі клітинки в межах довільного прямокутника із максимальною висотою та шириною, що не перевищують , у свій колір. Перший гравець фарбує клітинки в білий, а другий — у чорний колір. Після -го ходу підраховується остаточна кількість клітинок кожного кольору. Перемагає той гравець, у якого більше клітинок його кольору. Таким чином, мета кожного — максимізувати кількість клітинок свого кольору у фінальному результаті.
Напишіть програму, яка за початковим розфарбуванням, кількістю ходів і обмеженням на розмір прямокутника знаходить фінальну кількість клітинок кожного кольору за умови оптимальної гри обох гравців.
Перший рядок містить чотири додатних цілих числа: , , і (N \leq 400, M \leq 400, D \leq 400, K \leq 10^9) — висота і ширина поля, максимальний розмір прямокутника, який можна розфарбувати за один хід, і загальна кількість ходів. Далі йдуть рядків по символів: , якщо відповідна клітинка біла, і , якщо чорна.
Виведіть один рядок із двох цілих чисел — кількість білих і чорних клітинок у фінальному розфарбуванні поля за умови оптимальної гри обох гравців.
Приклад 1