Lim Li 正在她的后院经营一个蘑菇种植园。她的蘑菇种植园可以建模为一个 $R$ 行 $C$ 列的网格，每个网格方块可以是空的，也可以包含一个蘑菇，或者包含一个喷水器。例如，她的蘑菇种植园可能看起来像这样：
图 1：一个 $R = 5$ 且 $C = 5$ 的蘑菇农场。
喷水器和蘑菇之间的距离定义为它们在两个轴上坐标差的最大值。换句话说，如果蘑菇位于第 $X_m$ 行第 $Y_m$ 列，而喷水器位于第 $X_s$ 行第 $Y_s$ 列，它们之间的距离为 $\max(|X_s - X_m|, |Y_s - Y_m|)$。喷水器的覆盖范围有限，因此只有当喷水器与蘑菇之间的距离不超过 $D$ 时，喷水器才能浇灌该蘑菇。例如，如果 $D = 1$，两个喷水器可覆盖的区域将是：
图 2：显示喷水器覆盖范围的示意图。
蘑菇只有在有足够多的喷水器浇灌时才能生长并被收获。具体来说，如果一个蘑菇至少被 $K$ 个喷水器浇灌，那么它就是可收获的。请计算 Lim Li 在她的种植园中可以收获的蘑菇总数。
输入格式
输入的第一行包含四个整数：$R$（行数）、$C$（列数）、$D$（喷水器与被浇灌蘑菇之间的最大距离）以及 $K$（蘑菇可收获所需的最少喷水器数量）。
接下来的 $R$ 行输入每行包含 $C$ 个字符，表示蘑菇种植园的网格。每个字符代表特定网格方块的内容，如下所示：
- ‘.’ 表示空的网格方块，
- ‘M’ 表示包含蘑菇的网格方块，
- ‘S’ 表示包含喷水器的网格方块。
输出格式
输出包含一行一个整数，即 Lim Li 可以收获的蘑菇的最大数量。
子任务
每个实例的最大执行时间为 1.0 秒。你的程序将在满足以下限制的输入实例集上进行测试：
- $2 \le RC \le 500000$
- $1 \le D \le \max(R, C)$
- $1 \le K \le RC$
- 至少存在一个蘑菇
- 至少存在一个喷水器
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 9 | $1 \le R, C \le 100, D = \max(R, C), K = 1$ |
| 2 | 10 | $1 \le R, C \le 100, D = \max(R, C)$ |
| 3 | 18 | $1 \le R, C \le 100, D = 1, K = 1$ |
| 4 | 23 | $1 \le R, C \le 500$, 蘑菇数量 $\le 500$, 喷水器数量 $\le 500$ |
| 5 | 19 | $R = 1$ |
| 6 | 21 | - |
样例
样例输入 1
5 5 1 1 ....M .M... ..S.. .S... ...M.
样例输出 1
1
说明 1
由于每个喷水器的范围仅为 1，意味着喷水器只能到达相邻的方块，因此只有位于 $(2, 2)$ 的蘑菇被浇灌。
样例输入 2
4 4 4 1 .... .M.. ..MM ...S
样例输出 2
3
说明 2
由于每个喷水器的范围为 4，种植园中唯一的喷水器可以浇灌所有的蘑菇。
样例输入 3
1 8 5 2 SM..MM.S
样例输出 3
2
说明 3
每个蘑菇都需要两个喷水器在范围内，因为 $K = 2$。只有两个蘑菇满足此条件，即从左侧数起的第二个和第三个蘑菇。
样例输入 4
5 5 2 2 ....M .M... ..S.. .S... ...M.
样例输出 4
2
说明 4
由于每个喷水器的范围为 2，位于 $(2, 2)$ 的蘑菇和位于 $(5, 4)$ 的蘑菇都可以被两个喷水器浇灌。