AT_bitflyer2018_qual_d ハンコ

[problemUrl]: https://atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_d $ 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) $ の左上に合わせてハンコを押しました。 色が黒に変化したマスの個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ M $ $ A_1 $ $ A_2 $ $ : $ $ A_N $

答えを出力せよ。

### 制約 - $ 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 $ の各文字は `#` と `.` のいずれかである ### Sample Explanation 1 ハンコの左上をマス $ (1,\ 1) $, $ (1,\ 2) $, $ (2,\ 1) $, $ (2,\ 2) $ の $ 4 $ 箇所に合わせて押すことになります。 ハンコをこの順に押していった場合、各マスの色は下の図のように変化します。 すべての位置にハンコを押し終わったとき、色が黒に変化しているマスは $ 9 $ 個あります。 !\[abdf492090c7f44749c1243f34bae924.png\](https://img.atcoder.jp/bitflyer2018-qual/abdf492090c7f44749c1243f34bae924.png) ### Sample Explanation 2 真ん中以外のマスが黒くなります。