AT_s8pc_3_b 石落としゲーム

[problemUrl]: https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_b square1001氏は、パソコン部に入るために試験を受けました。 この試験の内容は、以下のようなものであります。 - $ H\ \times\ W $ の盤面が与えられる。 - その盤面の各マスは、 $ 1\ \sim\ 9 $ の数字が書かれている。また、1行目が一番上である。 - あなたは、セルのうち1つのマスを消すことができる。消した上のマスは落ちてくる。 また、そのゲームは以下のようなステップで進行する。 - 1:$ K $ 個以上の水平に隣り合うセルに同じ数字を彫った石があれば，これらの石は消滅する．こうした石群の消滅はすべて同時に起きる。 - 2:石が消滅したセルの上方のセルに石があれば，空きを埋めるように石が落下する。 - 3:すべての石の落下完了後に，消滅の条件を満たすようになった石群があれば，ステップ1に戻って繰り返す。 - 4:スコアは, $ 2^i\ \times\ \left(i\ \text{回目の消滅で消えた数字の値の和}\right) $ の合計である。ただし、最初の消滅を0回目とする。 そのとき、square1001氏が最適にやって試験に受かるか調べるために、最適にセルを消したときに何点取れるかを計算することにした。 square1001氏を助けるために、最大の点数を出力しなさい。

入力は以下の形式で標準入力から与えられる。/> > $ H\ W\ K $ $ c_{1,\ 1}\ c_{1,\ 2}\ \cdots\ c_{1,\ W} $ $ c_{2,\ 1}\ c_{2,\ 2}\ \cdots\ c_{2,\ W} $ $ \vdots\ \vdots\ \vdots $ $ c_{H,\ 1}\ c_{H,\ 2}\ \cdots\ c_{H,\ W} $ - 1行目に, 盤面の縦、横の大きさ$ H $, $ W $と、何個横に並ぶと消滅するかを表す数 $ K $ が与えられる。 - 2行目から, $ H $行にわたって盤面の状況が与えられる。 - `1`～`9`はそれぞれの数字があることを示す。

出力は以下の形式で標準出力に従うこと。 - 最大の点数を1行に出力しなさい。

### 制約 - $ 2\ \le\ H,\ W\ \le\ 30 $ - 点数は $ 1,000,000,000 $ 点を超えない - 最初の盤面では, すべての横に隣り合うマス同士は同じ数が書かれていることはない。 ### 小課題 小課題1 \[ $ 120 $ 点 \] - $ H,\ W\ \le\ 10 $ - $ W=K $ 小課題2 \[ $ 180 $点 \] - 追加の制約はない。 ### Sample Explanation 1 場所 $ (4,\ 3) $ を押すと以下のようになります。 !\[\](https://atcoder.jp/img/s8pc-3/f10e83a7d963f43415eb9afec2192501.png) よって, $ 7+16=23 $ 点となる。 また, 場所 $ (4,3) $ を消すのが最適である。 ### Sample Explanation 2 この入力例は小課題1の制約を満たさない。 ### Sample Explanation 3 この入力例は小課題1の制約を満たさない。 ### Sample Explanation 4 連鎖数が非常に大きくなることもある。