AT_bogosortcontest_div1_h Please Insert Coin

有一个纵向 $H$ 格、横向 $W$ 格的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的格子记为 $(i, j)$。每个格子 $(i, j)$ 中写有一个整数 $A_{i,j}$，表示该格子被放置方块的时刻。 时间从 $1$ 前进到 $K = \max(A_{i,j})$。数组 $A$ 满足以下性质： - 对于任意满足 $1 \le k \le K$ 的整数 $k$，至少存在一个格子 $(i,j)$ 使得 $A_{i,j} = k$。 - 具有相同值 $k$ 的格子集合，在上下左右方向上连通。 - 方块在每个列中从下往上依次堆积。也就是说，对于任意 $1 \le i \le H-1$ 和 $1 \le j \le W$，都有 $A_{i+1, j} \le A_{i, j}$。 在某个时刻，设第 $j$ 列已经堆积的方块数量为 $h_j$。初始状态下，所有列都有 $h_j = 0$。 soryuusi 君在初始状态下位于第 $s$ 列。对于时刻 $k = 1, 2, \dots, K$，游戏按顺序如下进行： 1. **soryuusi 君的移动**：soryuusi 君可以在网格内向左或向右移动到相邻的列，每次移动 $1$ 列，可以移动任意多次（也可以不移动，停留在当前列）。每从列 $x$ 移动到相邻的列 $y$ 一次，使用该时刻的方块高度消耗 $|h_x - h_y| + 1$ 的体力。 2. **方块的放置**：所有满足 $A_{i,j} = k$ 的格子都会被放置方块，对应列的 $h_j$ 分别增加该列新放置的方块数量。此时，如果 soryuusi 君当前所在的列有至少一个新方块被放置，那么 soryuusi 君会被压扁，游戏结束。 请判断 soryuusi 君能否在不游戏结束的情况下存活到时刻 $K$ 的方块放置结束。如果可以，请求出消耗体力的总计最小值。如果不可能存活，则输出 `-1`。 给定 $T$ 个测试用例，请分别求出答案。

输入按以下形式从标准输入给出。 > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每个测试用例按以下形式给出。 > $H$ $W$ $s$ > $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$ > $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$ > $\vdots$ > $A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$

输出共计 $T$ 行答案。第 $t$ 行输出第 $t$ 个测试用例的答案。即，消耗体力的最小值。如果不可能存活，则输出 `-1`。

### 样例解释 1 对于第 $1$ 个测试用例，soryuusi 君可以按如下方式行动，从而消耗体力 $10$。 - 移动到第 $4$ 列。消耗 $(|0 - 0| + 1) + (|0 - 0| + 1) + (|0 - 0| + 1) = 3$ 的体力。 - 时刻 $1$ 的方块被放置。 - 移动到第 $2$ 列。消耗 $(|0 - 1| + 1) + (|1 - 2| + 1) = 4$ 的体力。 - 时刻 $2$ 的方块被放置。 - 移动到第 $4$ 列。消耗 $(|2 - 2| + 1) + (|2 - 3| + 1) = 3$ 的体力。 - 时刻 $3$ 的方块被放置。 不可能以 $9$ 或更少的体力存活，因此消耗体力的最小值为 $10$。 对于第 $2$ 个测试用例，无论 soryuusi 君如何行动，都无法回避时刻 $2$ 的方块放置。因此该测试用例的输出为 `-1`。 ### 约束 - $1 \le T \le 10^5$ - $1 \le H, W$ - $H \times W \le 5 \times 10^5$ - $1 \le s \le W$ - $1 \le A_{i,j} \le H \times W \ (1 \le i \le H, 1 \le j \le W)$ - 对于任意满足 $1 \le k \le K$ 的整数 $k$，至少存在一个格子 $(i,j)$ 使得 $A_{i,j} = k$ - 满足 $A_{i,j} = k$ 的格子 $(i,j)$ 的集合，在上下左右方向上连通 - $A_{i+1, j} \le A_{i, j} \ (1 \le i \le H-1, 1 \le j \le W)$ - 所有测试用例中 $H \times W$ 的总和不超过 $5 \times 10^5$ - 输入中的所有数值均为整数 由 DeepSeek V4.1 Flash 翻译。