配点 : 500 点
問題文
H 行 W 有一张写着 列方格的纸。 从这个方格的上方数第 i 行,从左方数 j 列的方格(1 \leq i \leq H, 1 \leq j \leq W)称为方格 (i, j) 记作。
这个方格的 N 行 M 有一个大小与这些方格的列数相同的印章。 这个印章的印影由 N 个的长度 M 的字符串 A_1, A_2, ..., A_N 将印章的左上角对准方格 (s, t) (1 \leq s \leq H - N + 1, 1 \leq t \leq W - M + 1)的左上角 对齐后盖章,印章覆盖的各个方格 (u, v) (s \leq u \leq s + N - 1, t \leq v \leq t + M - 1)的颜色会如下变化。
- 文字列 A_i 的 j 第...个字符为
#时,方格 (s + i - 1, t + j - 1) 的颜色会变为黑色。 - 文字列 A_i 的 j 第...个字符为
.时,方格 (s + i - 1, t + j - 1) 的颜色不会发生变化。
最初,所有方格的颜色都是白色。 1 \leq s \leq H - N + 1, 1 \leq t \leq W - M + 1 对于满足...的每个 s, t , 将印章的左上角与方格 (s, t) 的左上角对齐后盖章。
请计算颜色变为黑色的方格数量。
制約
- 1 \leq H, W \leq 10^9
- 1 \leq N, M \leq 1000
- N \leq H
- M \leq W
- |A_i| = M (1 \leq i \leq N)
- 各 i 对于,A_i 的每个字符是
#和 我讨厌.中的某一个
入力
输入是按以下格式从标准输入给出的。
H W N M A_1 A_2 : A_N
出力
请输出答案。
入力例 1
3 4 2 3 ..# ##.
出力例 1
9
将印章的左上角对准格子后按下。 (1, 1), (1, 2), (2, 1), (2, 2) 的 4 将按照相应位置按下印章。 如果按照这个顺序依次按下印章,各个格子的颜色会如图所示发生变化。
在所有位置都按下印章后,颜色变为黑色的格子有 9 个。
入力例 2
5 5 4 4 #### #..# #..# ####
出力例 2
24
除正中央以外的格子都会变黑。
入力例 3
10 12 1 1 .
出力例 3
0
入力例 4
20 20 5 5 ##.## .##.# ..##. ...## ....#
出力例 4
390
入力例 5
1000000000 1000000000 5 4 .#.. .... ..#. .#.. ....
出力例 5
999999996999999999