eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

Input data

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

Output data

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

Examples

Input example #1
3 3 2 1
BWB
BBW
WBB
Output example #1
6 3
Author Роман Едемский
Source 2012 XXV All-Ukrainian Informatics Olympiad, Vinnitsa, March 24 - 28, Round 2