老猫下山

Problem Description

深山之中，住着一位得道的老猫。其弟子 jimmyywang 每日跟随它修行。他们所居住的这座灵山，可以看作一个 $n \times m$ 的区域。山中万物皆有灵，每个区域的灵力都处在一个特定的境界，从 $0$ 到 $k-1$ 共 $k$ 种。 老猫认为，当整座山的灵力境界归于统一之时，世界的灵力才能达到和谐。 调和整座山的灵力是一项艰巨的任务，可能需要进行多次修行才能完成。 一个完整的修行方案包含任意次下山行程。在每一次行程中，老猫都会选择一条从山顶 $(1,1)$ 到山脚 $(n,m)$ 的路径。由于是下山，它的每一步只能移动到相邻的下方格子 $(i+1, j)$ 或右方格子 $(i, j+1)$。每次走完一条路径，路径上所有格子的灵力境界都会因其灵力而提升一阶。如果一个格子的境界已经是 $k-1$，则会回归到最初的境界 $0$（即，境界变化是在模 $k$ 意义下加 $1$）。 穿行每个格子 $(i,j)$ 都会消耗老猫的精力，其消耗量为 $a_{i,j}$。这个值是非负的。一次下山行程的精力成本，是路径上所有格子 $a_{i,j}$ 值的总和。 作为弟子的 jimmyywang，他的任务是设计一套总精力成本最小的修行方案（即，规划所有必要的下山行程），使得在方案执行完毕后，整座山的 $n \times m$ 个格子能变为同一种境界（即，所有格子的境界值都等于某一个共同的值 $c$，其中 $0 \le c < k$）。方案的总成本是所有行程成本的累加。 但是 jimmyywang 还要打音游，所以请你帮帮他！ 形式化的，给定一个 $n \times m$ 的网格，每个格子 $(i,j)$ 有一个初始境界 $s_{i,j}$（一个 $0$ 到 $k-1$ 的整数）和一个非负的成本 $a_{i,j}$。 你可以执行任意次以下操作（一次操作定义为依次进行以下三条）：

• 选择一条从 $(1,1)$ 到 $(n,m)$ 的路径，路径每一步只能从 $(i,j)$ 移动到 $(i+1,j)$ 或 $(i,j+1)$。
• 将路径上所有格子的境界值加 $1$（在模 $k$ 意义下）。
• 该次操作的成本为路径上所有格子的成本 $a_{i,j}$ 之和。 你的目标是使得整个网格的境界统一（所有格子的值都等于同一个整数），并求出达成该目标所需的最小总成本。

Input

第一行包含一个整数 $T$（$1\le T \le 10$），表示测试数据的组数。 接下来，对于每组测试数据：

• 第一行包含三个整数 $n, m, k$（$1\le n,m\le 100$，$2\le k\le 100$），表示灵山的尺寸和境界的总数。
• 接下来 $n$ 行，每行 $m$ 个整数，表示每个格子 $(i,j)$ 的初始境界 $s_{i,j}$（$0\le s_{i,j} \le k$）。
• 再接下来 $n$ 行，每行 $m$ 个整数，表示穿行每个格子 $(i,j)$ 所对应的精力消耗 $a_{i,j}$（$0\le a_{i,j} \le 1000$）。

Output

对于每组测试数据，输出一行，包含一个整数，代表达成和谐状态所需的最小总精力成本。如果无论如何都无法使整座山变为同色，则输出 Impossible。

Sample Input

1
3 3 5
0 1 0
2 2 0
4 3 0
2 0 7
0 3 200
100 10 1

Sample Output

1178

Hint

一种最优方案是：

• 路径 $(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)$ 走 3 次，成本为 $3\times(2+0+7+200+1)=630$。
• 路径 $(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)$ 走 4 次，成本为 $4\times(2+0+3+10+1)=64$。
• 路径 $(1,1)\to(2,1)\to(2,2)\to(3,2)\to(3,3)$ 走 2 次，成本为 $2\times(2+0+3+10+1)=32$。
• 路径 $(1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)$ 走 4 次，成本为 $4\times(2+0+100+10+1)=452$。 容易验证经过这些操作后，所有数都会变成 3。总代价和是 $630+64+32+452=1178$，可以证明没有成本更低的方案。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）