很久以前，Zenyk 为他的朋友们发明了一种新的魔法游戏。他拿来一个 $n \times m$ 的棋盘，并在上面放置了 $k$ 个水晶。之后，他又在棋盘上放置了 $b$ 个炸弹。

爆炸时，每个炸弹会摧毁其所在行或所在列的所有水晶。它还会引爆所选方向上的所有其他炸弹。每个炸弹的爆炸方向（行或列）由朋友们选择。不同的炸弹可以选择不同的方向。

游戏的目标是选择第一个炸弹以及每个炸弹的引爆方向，使得被摧毁的水晶数量尽可能多。

第一行包含四个整数：$n, m, k, b$ ($1 \le n, m \le 3000, 0 \le k + b \le n \cdot m$)。它们分别代表棋盘的尺寸、水晶的数量以及炸弹的数量。

接下来的 $n$ 行，每行包含 $m$ 个字符，用于描述棋盘：

• “.” — 空单元格，
• “k” — 水晶，
• “b” — 炸弹。

输出一个整数：可能被摧毁的水晶的最大数量。

样例

输入格式 1

7 3 4 5
bbb
..b
..b
k..
k..
k..
k..

输出格式 1

4

输入格式 2

3 3 4 2
k..
kk.
bbk

输出格式 2

3