P13178 [GCJ 2017 #3] Slate Modern

著名的 Slate Modern 画廊专注于最新的艺术潮流：遵循严格规则的灰度画作。画廊中的每一幅画都必须是一个有 $R$ 行 $C$ 列的网格。网格中的每个格子都被涂上一个正整数的亮度值；为了避免画面过于刺眼，任何两个有公共边（不仅仅是角）的格子的亮度值之差不能超过 $D$。 你的艺术家朋友 Cody-Jamal 正在为画廊创作一幅画。昨晚，他灵感迸发，已经在 $N$ 个不同的特定格子里填入了某些正整数亮度值。你今天才告诉他画廊的规则，现在他想知道，是否有可能为剩下的所有格子填入正整数亮度值，并完成这幅画，同时不违反画廊的规则。如果可以，他希望所有亮度值的总和尽可能大，以节省黑色颜料。你能帮他求出这个最大可能的亮度总和，或者判断任务是否不可能完成吗？由于结果可能非常大，你只需要输出结果对质数 $10^9 + 7$（$1000000007$）取余后的值。

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为四个整数：$R$、$C$、$N$ 和 $D$，含义如上所述。接下来的 $N$ 行，每行有三个整数 $R_i$、$C_i$ 和 $B_i$，表示第 $R_i$ 行第 $C_i$ 列的格子的亮度值为 $B_i$。网格的行和列编号均从 1 开始。

对于每组测试数据，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最大可能的亮度总和对 $10^9 + 7$ 取余的结果；如果无法完成画作，则输出 `IMPOSSIBLE`。

**样例解释** 样例 1 中，最优的填法如下： ``` 6 7 9 4 6 8 ``` 总和为 $40$。 样例 2 中，最优的填法如下： ``` 2000000000 1000000000 ``` 总和为 $3000000000$；对 $10^9 + 7$ 取余后为 $999999986$。 样例 3 中，任务无法完成。无论你为第 2 行的格子选择什么值，它与已填的相邻格子的亮度差都会超出允许范围。 样例 4 中，Cody-Jamal 已经填入的两个格子的亮度值差距过大，因此无法继续完成画作。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq N \leq 200$。 - $1 \leq D \leq 10^9$。 - $1 \leq R_i \leq R$，对于所有 $i$。$1 \leq C_i \leq C$，对于所有 $i$。$1 \leq B_i \leq 10^9$，对于所有 $i$。（注意，上界仅适用于 Cody-Jamal 已经填入的格子。你可以为其他格子分配大于 $10^9$ 的亮度值。） - $N < R \times C$。（至少有一个空格子。） - 对于所有 $i \neq j$，有 $R_i \neq R_j$ 或 $C_i \neq C_j$。（所有已知格子均不相同。） **小数据范围（5 分，测试点 1 - 可见）** - 时间限制：10 秒。 - $1 \leq R \leq 200$。 - $1 \leq C \leq 200$。 **大数据范围（26 分，测试点 2 - 隐藏）** - 时间限制：20 秒。 - $1 \leq R \leq 10^9$。 - $1 \leq C \leq 10^9$。 由 ChatGPT 4.1 翻译