Coloring
On the planet Olympia, an annual traditional game called "Coloring" takes place. The game is played on a large Olympic field of size N×M, where each cell is initially painted either white or black. Two players participate, taking turns to make a total of exactly K moves. During a player's turn, they can paint all the cells within any one rectangle with their color, as long as the rectangle's height and width do not exceed D. The first player paints the cells white, while the second player paints them black. After the K-th move, the game's final score is determined by counting the number of cells of each color. The player with more cells of their color wins. Thus, each player aims to maximize the number of cells in their color by the end of the game.
Your task is to write a program that, given the initial coloring of the field, the number of moves, and the rectangle size restrictions, calculates the final score of the game assuming both players use optimal strategies.
Input
The first line contains four natural numbers: N, M, D, and K (N ≤ 400, M ≤ 400, D ≤ 400, K ≤ 10^9)—representing the height and width of the field, the maximum size of the rectangle a player can paint, and the total number of moves. The next N lines each contain M characters: W for a white cell and B for a black cell.
Output
Output 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.