The Destruction of the Crystals

Once upon a time, Zenyk came up with a new magical game for his friends. He brought an $n \times m$ board and placed $k$ crystals on it. After that, he also placed $b$ bombs on the board.

Upon explosion, each bomb destroys all the crystals either in its row or in its column. It also detonates all the bombs in the chosen direction. The direction of the explosion (row or column) for each bomb is chosen by the friends. Different bombs may have different directions.

The objective of the game is to choose the first bomb and the directions to detonate in such a way that the number of destroyed crystals is the largest possible.

The first line contains four integers $n$, $m$, $k$, $b$ ($1 \le n, m \le 3000$, $0 \le k + b \le n \times m$). They are the dimensions of the board, the number of crystals on it, and the number of bombs.

The next $n$ lines describe the board with $m$ characters per line:

• "." is an empty cell,
• "k" is a crystal,
• "b" is a bomb.

Print a single integer: the maximum possible number of destroyed crystals.