Problem Description

Square1001 is taking an exam to join the computer club.
The content of this exam is as follows:

• A board of size $H \times W$ is given.
• Each cell on the board contains a number from $1 \sim 9$. The first row is the topmost.
• You can erase one cell. The cells above the erased cell will drop down.

The game proceeds in the following steps:
- 1: If there are $ K $ or more horizontally adjacent cells with the same number, these stones disappear. All such groups of stones disappear simultaneously.
- 2: If stones have disappeared, the stones above them fall to fill the empty spaces.
- 3: After all stones have finished falling, if any new groups of stones meet the disappearance condition, return to step 1.
- 4: The score is the sum of $2^i \times \left(the sum of the values of the stones disappeared in the i-th disappearance\right)$. The initial disappearance is considered the 0th.

To help Square1001 determine if he can pass the exam by playing optimally, calculate the maximum score he can achieve by erasing cells optimally.
Output the maximum score.

Input Format

Input is given from the 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}$

• The first line contains the vertical and horizontal sizes of the board $ H $, $ W $, and the number $ K $ representing how many horizontally adjacent cells must have the same number to disappear.
• The next $ H $ lines describe the board's state.
• 1 to 9 indicate the presence of the respective numbers.

Output Format

Output should follow the standard output format:

• Output the maximum score on one line.

Sample Input and Output

Sample Input #1

4 4 2
3413
4121
1424
2312

Sample Output #1

23

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

Notes/Hints

Constraints

• $2 \le H, W \le 30$
• The score does not exceed $ 1,000,000,000 $
• Initially, no horizontally adjacent cells on the board have the same number.

Subtasks

Subtask 1 \[ $ 120 $ points \]

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

Subtask 2 \[ $ 180 $ points \]

• No additional constraints.

Sample Explanation 1

Pressing the location $ (4, 3) $ results in the following:  Thus, the score is $ 7 + 16 = 23 $. Also, erasing the location $ (4, 3) $ is optimal.

Sample Explanation 2

This input example does not satisfy the constraints of Subtask 1.

Sample Explanation 3

This input example does not satisfy the constraints of Subtask 1.

Sample Explanation 4

The number of chains can be very large.

见题面 Input 部分

见题面 Output 部分