题目描述

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行に出力しなさい。

题目大意

square1001参加了计算机部的入学考试。 这个考试的内容如下：

给定一个 $H\ \times\ W$ 的棋盘。

棋盘上的每个格子上都写着数字 $1\ \sim\ 9$。第一行是最上面的一行。

你可以消除一个格子中的数字，消除后上面的格子会掉下来。

此外，游戏的进行按照以下步骤进行。

1：如果有 $K$ 个或更多水平相邻的格子上有相同的数字，这些格子会消失。这些石块的消失是同时进行的。

2：消失的格子上方有石块的话，石块会下落填充空位。

3：在所有石块下落完成后，如果存在满足消失条件的石块群，则返回步骤1并重复。

4：得分是 $2^i\ \times\ \left(i\ \text{次消失时消失的数字的和}\right)$ 的总和。其中，第一次消失为第0次。

在这种情况下，为了确定square1001氏能否以最佳方式通过考试，决定计算在最佳情况下消除格子时可以获得多少分。 为了帮助square1001，输出最高得分。

4 4 2
3413
4121
1424
2312

23

4 4 2
1212
2121
1212
2121

54

7 7 2
8989898
9898989
8989898
9898989
8989898
9898989
8989898

2520

17 17 2
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
91234567891234567
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456

2354638

提示

制約

• $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)$ を押すと以下のようになります。  よって, $7+16=23$ 点となる。 また, 場所 $(4,3)$ を消すのが最適である。

Sample Explanation 2

この入力例は小課題1の制約を満たさない。

Sample Explanation 3

この入力例は小課題1の制約を満たさない。

Sample Explanation 4

連鎖数が非常に大きくなることもある。