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

Раскрашивание

Раскрашивание

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

На планете Олимпия ежегодно проводится традиционная игра в "Раскраски". Местом проведения этой игры является большое олимпийское поле N×M, каждая клетка которого окрашена в белый или в черный цвет. Двое игроков ходят по очереди, и суммарно совершают на двоих ровно K ходов. Во время своего хода игроку разрешается закрасить собственным цветом все клетки любого одного прямоугольника чья высота и ширина не превышает D. Первый игрок закрашивает клетки в белый цвет, а второй – в черный. По окончании K-го хода подсчитывается окончательный счет игры – количество клеток каждого цвета. Победителем оглашается тот игрок, в чей цвет раскрашено большее число клеток чем у соперника. Поэтому, целью каждого игрока есть максимизация количества клеток его собственного цвета в окончательном варианте раскраски поля.

Напишите программу, которая по начальной раскраске, количеству ходов и ограничениям на прямоугольник, который может закрашивать игрок, найдет окончательный счет игры при оптимальной стратегии обоих игроков.

Вхідні дані

Первая строка содержит четыре натуральных числа: N, M, D и K (N 400, M400, D 400, K 10^9) - высота и ширина поля, ограничение на размер прямоугольника, который может закрашивать игрок, количество ходов, которые предстоит выполнить до подведения окончательного счета. В последующих N строках расположено по M символов: W если соответствующая клетка раскрашена в белый цвет и B, в случае если клетка поля раскрашена в черный цвет.

Вихідні дані

Единственная строка должна содержать два целых числа – количество белых и количество черных клеток в окончательном варианте раскраски при условии оптимальной игры обоих игроков.

Приклад

Вхідні дані #1
3 3 2 1
BWB
BBW
WBB
Вихідні дані #1
6 3
Автор Роман Едемський
Джерело 2012 XXV Всеукраїнська олімпіада з інформатики, Вінниця, Березень 24 - 28, тур 2