1026 - Takenoko Kinoko Cultivation

間違い修正完了　たぶん解けます 20181213

ストーリー

ei1821は筍派(急進派)である。

ei1821はビニールハウスでたけのこときのこを栽培している。 最新の科学技術により、とある薬品Aをきのこにかけると筍に、とある薬品Bをたけのこにかけると茸になる。
薬品をかける機械は上から撒布するが、撒く薬品は機械が自動的に判断し、1辺がNmの平方形の範囲に撒かれる。
栽培区間は一辺1mの正方形で区切られており、各区間に1つずつたけのこもしくはきのこが栽培されている。
薬品は対応したほうにしか使えず、絶対に混合してはならない。薬品Aをたけのこにかけたり、
薬品Bをきのこにかけるなどの愚行は絶対にあってはならない。
それがいけないので全て機械に任せているのだが、とある問題が発生した。
たけのこときのこの栽培位置が完全に混ざっているのだ。
これではもし適当に撒いたら愚行が起こりかねないが、機械は正確に判断するためそんな愚行は起こりえない。
薬品はたくさん掛けられても何ら問題はなく、もし撒布されなくても問題はない。
よって、薬品が混ざることがだめなのだ。
機械が薬品を撒布することが出来る箇所の総数を求めよ。

入力

1行目に、たけのこときのこを栽培している空間の長さHとWが与えられる
2行目に、薬品を撒布する平方形の一辺の長さNが与えられる
3行目からH+2行目に渡ってビニールハウス内マップの栽培状況のデータが与えられる。データは二種類である。
'k'はきのこである。これには薬品Aをかけてよい。
't'はたけのこである。これには薬品Bをかけてよい。

H W
n
map0 0   map0 １   ...   map0 W-1
map1 0   map1 1   ...   map1 W-1
... ...
mapH-1 0   mapH-1 1   ...   mapH-1 W-1

出力

機械が薬品を撒布できる箇所の総数を出力せよ。 最後の改行を忘れずに。

制約

• 2 ≤ $H$, $W$ ≤ 5000
• 1 ≤ $N$ ≤ min(9,H,W)

入出力例

例1

入力

5 5
2
ttkkt
ttkkt
kkktt
kkktt
ttttt

出力

6

例1ではきのこに3回、たけのこに3回撒布しているので合計の6を出力する。

例2

入力

5 5
2
kkttk
kkttk
tttkk
tttkk
kkkkk

出力

6

もちろん位置が逆でも出力に変化はない。

例3

入力

20 20
3
ttktkkkkkttttktkkktt
tkkkttkttttttktttkkk
tttkktktttktkkkkkkkk
ktttkttkktktkkkkkttt
kkkktktktkktkkkktktt
kktktkkktttttttkkttk
tkkktttkkkttkkktkkkk
ktkttkttktttkktktktt
tttktktktkkkktkkkktt
ktkkktttktkktkkttktt
ktktttttttktkkktkttk
tkktkktkktktktkktkkt
ktktkttkkkttkktkttkk
kktktktttkktkkktkktk
tkkttktktttkkkkttttt
ttkkttkttkktttkttktt
tttttktktkkktktktttk
tttktktktkkktttttktk
tktkktttttktkkkttktt
kkkktkkktktttkttkkkk

出力

2

3行目から5行目に掛けてきのこの固まりが2つずつある。