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 翻译