Contest Duration: - (local time) (180 minutes)
B - Falling Stone Game /

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $300$ Points

### Problem Statement

We are playing a puzzle. An upright board with $H$ rows by $W$ columns of cells, is used in this puzzle.
A stone in $i$-th row and $j$-th column engraved with a digit, one of 1 through 9, is placed in each of the cells.
You can erase 1 cell in the board.

The game process is following:
1. When $K$ or more stones in horizontally adjacent cells are engraved with the same digit, the stones will disappear. Disappearances of all such groups of stones take place simultaneously.
2. When stones are in the cells above the emptied cells, these stones drop down so that the emptied cells are filled.
3. After the completion of all stone drops, if one or more groups of stones satisfy the disappearance condition, repeat by returning to the step 1.
4. Score is $\sum_i 2^i \times \left(\text{Sum of numbers in the stones which disappeared in the$i$-th chain (0-indexed)}\right)$.
Please answer the points if he erased the optimal place.

### Input

The input is given from standard input in the following format.
$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}$

### Output

• Please output total points if he erase the optimal place.

### Constraints

• $2 \le H, W \le 30$
• $2 \le K \le 3$
• $answer \le 1,000,000,000$
• $c_{i,j} ≠ c_{i,j+1} (1 \le j \le W-1)$

### Subtasks

Subtask 1 [ $120$ points ]
• $H, W \le 10$
• $W=K$
Subtask 2 [ $180$ points ]
• There are no additional constraints.

### Sample Input 1

4 4 2
3413
4121
1424
2312


### Sample Output 1

23

If you erase cell(4,3):

Total score: $7 + 16 = 23$points.
The optimal place to erase is cell(3,2).

### Sample Input 2

4 4 2
1212
2121
1212
2121


### Sample Output 2

54


### Sample Input 3

7 7 2
8989898
9898989
8989898
9898989
8989898
9898989
8989898


### Sample Output 3

2520


### Sample Input 4

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


### Sample Output 4

2354638

writer: E869120

### 問題文

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$行にわたって盤面の状況が与えられる。
• 19はそれぞれの数字があることを示す。

### 出力

• 最大の点数を1行に出力しなさい。

### 制約

• $2 \le H, W \le 30$
• 点数は $1,000,000,000$ 点を超えない
• 最初の盤面では, すべての横に隣り合うマス同士は同じ数が書かれていることはない。

### 小課題

• $H, W \le 10$
• $W=K$

• 追加の制約はない。

### 入力例1

4 4 2
3413
4121
1424
2312


### 出力例1

23


よって, $7+16=23$ 点となる。
また, 場所 $(4,3)$ を消すのが最適である。

### 入力例2

4 4 2
1212
2121
1212
2121


### 出力例2

54

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

### 入力例3

7 7 2
8989898
9898989
8989898
9898989
8989898
9898989
8989898


### 出力例3

2520

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

### 入力例4

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


### 出力例4

2354638