CF1353F Decreasing Heights

你正在玩一款著名的沙盒游戏，其世界是三维的。这个世界的地图可以表示为一个 $n \times m$ 的矩阵，其中第 $(i, j)$ 个格子的高度为 $a_{i, j}$。 你现在位于格子 $(1, 1)$，想要到达格子 $(n, m)$。你只能向下（从格子 $(i, j)$ 到格子 $(i+1, j)$）或向右（从格子 $(i, j)$ 到格子 $(i, j+1)$）移动。还有一个额外的限制：如果当前格子的高度为 $x$，那么你只能移动到高度为 $x+1$ 的格子。 在第一次移动之前，你可以进行若干次操作。每次操作，你可以将任意一个格子的高度减少 $1$。也就是说，你可以选择某个格子 $(i, j)$，并将其高度设置为 $a_{i, j} := a_{i, j} - 1$。注意，高度可以减少到小于等于 $0$。同时，你也可以减少格子 $(1, 1)$ 的高度。 你的任务是，求出你至少需要进行多少次操作，才能使得从格子 $(1, 1)$ 到格子 $(n, m)$ 至少存在一条合法路径。保证一定存在解。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$），表示地图的行数和列数。接下来的 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行第 $j$ 个整数为 $a_{i, j}$（$1 \le a_{i, j} \le 10^{15}$），表示格子 $(i, j)$ 的高度。 保证所有测试用例中 $n$ 的总和不超过 $100$，$m$ 的总和也不超过 $100$（$\sum n \le 100; \sum m \le 100$）。

对于每组测试用例，输出一个整数，表示你至少需要进行多少次操作，才能使得从格子 $(1, 1)$ 到格子 $(n, m)$ 至少存在一条合法路径。保证一定存在解。

由 ChatGPT 4.1 翻译