問題
HOJ鉱山会社では掘削機を使って鉱物を掘ることで収入を得ています。あるとき、HOJ鉱山会社は鉱床が記述されている地図を入手しました。そこでHOJ鉱山会社はこの地図に書いてある土地で掘削機を使って鉱物を堀り収入を得ようと考えました。しかしHOJ会社は貧乏なので掘削機は一つしか持っていません。また人を雇う余裕がないためどこに配置すればどれくらい利益を得られるか分かりません。あなたはそんなHOJ鉱山会社の代わりに得られる最大の利益を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$H$ $W$ $L$
$C_{0,0}$ $C_{0,1}$ ... $C_{0,W}$
$C_{1,0}$ $C_{1,1}$ ... $C_{1,W}$
:
$C_{H,0}$ $C_{H,1}$ ... $C_{H,W}$
1行目に地図の高さ$H$, 幅$W$, 採掘機の一辺の長さ$L$が与えられる。
2行目から$H$行にかけて地図の情報が与えられる。
- . : 地面を表す
- # : 壁を表す
- * : 鉱床を表す
出力
出力の最後に改行を入れること。
1行目にその地図で得られる最大の利益の値を出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq H, W \leq 10^{3}$
- $1 \leq L \leq min(H, W)$
入出力例
入力例1
5 5 2 *#### ..*.# .*.#. *#.*# .###.
出力例1
2
(2,2)から(3,3)にかけて掘削機を配置すると鉱床が二つ得られます。これが最大となります。
入力例2
2 2 2 #* **
出力例2
0
(1,1)にある壁が邪魔をして掘削機を配置できないので0になります。
入力例3
5 5 2 *#### ..*.# .*##. *#.** ....#
出力例3
1