D - ハンコ

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500

問題文

HW 列のマス目が書かれた紙があります。 このマス目の上から i 行目、左から j 列目のマス (1 \leq i \leq H, 1 \leq j \leq W) をマス (i, j) と書きます。

このマス目の NM 列ぶんと同じ大きさのハンコがあります。 このハンコの印影は 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_ij 文字目が # であるとき、マス (s + i - 1, t + j - 1) の色は黒に変化する。
  • 文字列 A_ij 文字目が . であるとき、マス (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 個あります。

abdf492090c7f44749c1243f34bae924.png

入力例 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