AT_s8pc_3_b.石落としゲーム

square1001 为了加入计算机社团参加了一场考试。
这场考试的内容如下：

• 给定一个 $H \times W$ 的棋盘。
• 棋盘上的每个格子上都写有 $1 \sim 9$ 的数字。第 1 行在最上面。
• 你可以选择消除棋盘上的任意一个格子。被消除格子上方的格子会下落补位。

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

• 1：如果有 $K$ 个或以上水平相邻的格子上写有相同的数字，这些格子会被同时消除。
• 2：被消除的格子上方如果有石头，则会下落填补空位。
• 3：所有石头下落完成后，如果又出现满足消除条件的石头群，则回到步骤 1 继续进行。
• 4：得分为 2^i \times \left(第 $i$ 次消除时被消除数字的总和\right) 的总和。注意，第一次消除为第 0 次。

现在，为了帮助 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$。
• 接下来 $H$ 行，每行 $W$ 个数字，表示棋盘的状态。
• 1～9 表示对应的数字。

请输出最大得分，输出一行。

约束条件

• $2 \leq H, W \leq 30$
• 得分不会超过 $1,000,000,000$
• 初始棋盘上，任意横向相邻的格子都不会有相同的数字。

小任务

小任务 1 [$120$ 分]

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

小任务 2 [$180$ 分]

• 无其他额外约束。

样例解释 1

如果消除位置 $(4, 3)$，棋盘会变为如下所示：

因此，得分为 $7+16=23$。
消除 $(4,3)$ 是最优选择。

样例解释 2

该输入样例不满足小任务 1 的约束。

样例解释 3

该输入样例不满足小任务 1 的约束。

样例解释 4

连锁消除次数可能会非常多。

由 ChatGPT 4.1 翻译