Coloring#3039
On planet Olympia, the traditional annual "Coloring" game takes place. The game is played on a large field of size N \times M, where each cell is initially colored either white or black. Two players play in turns, making a total of exactly moves. On each move, a player can recolor all the cells within any single rectangle so that its height and width do not exceed , painting them with their own color. The first player paints cells white, and the second player paints cells black. After the -th move, the final score is determined by counting the number of cells of each color. The player with more cells of their color wins. Thus, the goal of each player is to maximize the number of cells of their own color in the final coloring.
Write a program that, given the initial coloring, the number of moves, and the restriction on the size of the rectangles that can be colored, finds the final count for each color assuming optimal play by both players.
The first line contains four positive integers: , , , and (N \leq 400, M \leq 400, D \leq 400, K \leq 10^9) — the height and width of the field, the maximum size of the rectangle a player can recolor, and the total number of moves. The next lines contain characters each: if the respective cell is white, and if the cell is black.
Print a single line with two integers — the number of white and black cells in the final coloring of the field, assuming optimal play by both players.
Example 1