AT_abc383_b [ABC383B] Humidifier 2

[problemUrl]: https://atcoder.jp/contests/abc383/tasks/abc383_b AtCoder社のオフィスは $ H $ 行 $ W $ 列のマス目で表されます。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ と表します。 各マスの状態は文字 $ S_{i,j} $ で表され、 $ S_{i,j} $ が `#` のときそのマスは机、`.` のときそのマスは床です。床のマスは $ 2 $ つ以上存在することが保証されます。 あなたは床のマスから異なる $ 2 $ マスを選び、加湿器を設置します。 加湿器が設置されたとき、あるマス $ (i,j) $ は加湿器があるマス $ (i',j') $ からのマンハッタン距離が $ D $ 以下であるとき、またその時に限り加湿されます。 なお、マス $ (i,j) $ からマス $ (i',j') $ までのマンハッタン距離は $ |i-i'|+|j-j'| $ で表されます。 ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。 加湿される **床のマス** の個数として考えられる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ D $ $ S_{1,1} $$ S_{1,2} $$ \cdots $$ S_{1,W} $ $ S_{2,1} $$ S_{2,2} $$ \cdots $$ S_{2,W} $ $ \vdots $ $ S_{H,1} $$ S_{H,2} $$ \cdots $$ S_{H,W} $

答えを出力せよ。

### 制約 - $ 1\ \leq\ H\ \leq\ 10 $ - $ 1\ \leq\ W\ \leq\ 10 $ - $ 2\ \leq\ H\ \times\ W $ - $ 0\ \leq\ D\ \leq\ H+W-2 $ - $ H,W,D $ は整数 - $ S_{i,j} $ は `#` または `.` である $ (1\ \leq\ i\ \leq\ H,\ 1\ \leq\ j\ \leq\ W) $ - 床のマスは $ 2 $ つ以上存在する ### Sample Explanation 1 マス $ (1,1) $ とマス $ (1,5) $ に加湿器を置いた時: - マス $ (1,1) $ の加湿器によってマス $ (1,1),(2,1) $ の $ 2 $ マスが加湿されます。 - マス $ (1,5) $ の加湿器によってマス $ (1,5) $ の $ 1 $ マスが加湿されます。 よって、合計 $ 3 $ マス加湿されています。また、$ 4 $ マス以上加湿するような加湿器の置き方は存在しないため、答えは $ 3 $ です。 ### Sample Explanation 2 マス $ (2,4) $ とマス $ (5,3) $ に加湿器を置いた時、$ 15 $ 個の床のマスが加湿されます。