Раскрашивание
Раскрашивание
На планете Олимпия ежегодно проводится традиционная игра в "Раскраски". Местом проведения этой игры является большое олимпийское поле N×M, каждая клетка которого окрашена в белый или в черный цвет. Двое игроков ходят по очереди, и суммарно совершают на двоих ровно K ходов. Во время своего хода игроку разрешается закрасить собственным цветом все клетки любого одного прямоугольника чья высота и ширина не превышает D. Первый игрок закрашивает клетки в белый цвет, а второй – в черный. По окончании K-го хода подсчитывается окончательный счет игры – количество клеток каждого цвета. Победителем оглашается тот игрок, в чей цвет раскрашено большее число клеток чем у соперника. Поэтому, целью каждого игрока есть максимизация количества клеток его собственного цвета в окончательном варианте раскраски поля.
Напишите программу, которая по начальной раскраске, количеству ходов и ограничениям на прямоугольник, который может закрашивать игрок, найдет окончательный счет игры при оптимальной стратегии обоих игроков.
Input data
Первая строка содержит четыре натуральных числа: N, M, D и K (N ≤ 400, M ≤ 400, D ≤ 400, K ≤ 10^9) - высота и ширина поля, ограничение на размер прямоугольника, который может закрашивать игрок, количество ходов, которые предстоит выполнить до подведения окончательного счета. В последующих N строках расположено по M символов: W если соответствующая клетка раскрашена в белый цвет и B, в случае если клетка поля раскрашена в черный цвет.
Output data
Единственная строка должна содержать два целых числа – количество белых и количество черных клеток в окончательном варианте раскраски при условии оптимальной игры обоих игроков.
Examples
3 3 2 1 BWB BBW WBB
6 3