P13178 [GCJ 2017 #3] Slate Modern

The prestigious Slate Modern gallery specializes in the latest art craze: grayscale paintings that follow very strict rules. Any painting in the gallery must be a grid with $\mathbf{R}$ rows and $\mathbf{C}$ columns. Each cell in the grid is painted with a color of a certain positive integer brightness value; to make sure the art is not too visually startling, the brightness values of any two cells that share an edge (not just a corner) must differ by no more than $\mathbf{D}$ units. Your artist friend Cody-Jamal is working on a canvas for the gallery. Last night, he became inspired and filled in $\mathbf{N}$ different particular cells with certain positive integer brightness values. You just told him about the gallery's rules today, and now he wants to know whether it is possible to fill in all of the remaining cells with positive integer brightness values and complete the painting without breaking the gallery's rules. If this is possible, he wants to make the sum of the brightness values as large as possible, to save his black paint. Can you help him find this sum or determine that the task is impossible? Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime $10^9 + 7$ ($1000000007$).

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case begins with one line with four integers: $\mathbf{R}$, $\mathbf{C}$, $\mathbf{N}$, and $\mathbf{D}$, as described above. Then, $\mathbf{N}$ lines follow; the $i$-th of these has three integers $\mathbf{R}_i$, $\mathbf{C}_i$, and $\mathbf{B}_i$, indicating that the cell in the $\mathbf{R}_i$th row and $\mathbf{C}_i$th column of the grid has brightness value $\mathbf{B}_i$. The rows and columns of the grid are numbered starting from 1.

For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from 1) and $y$ is either IMPOSSIBLE if it is impossible to complete the picture, or else the value of the maximum possible sum of all brightness values modulo the prime $10^9 + 7$ ($1000000007$).

**Sample Explanation** In Sample Case #1, the optimal way to finish the painting is: ``` 6 7 9 4 6 8 ``` and the sum is $40$. In Sample Case #2, the optimal way to finish the painting is: ``` 2000000000 1000000000 ``` and the sum is $3000000000$; modulo $10^9 + 7$, it is $99999998$6. In Sample Case #3, the task is impossible. No matter what value you choose for the cell in row $2$, it will be too different from at least one of the two neighboring filled-in cells. In Sample Case #4, the two cells that Cody-Jamal filled in already have brightness values that are too far apart, so it is impossible to continue. **Limits** - $1 \leq \mathbf{T} \leq 100$. - $1 \leq \mathbf{N} \leq 200$. - $1 \leq \mathbf{D} \leq 10^9$. - $1 \leq \mathbf{R}_i \leq \mathbf{R}$, for all $i$. $1 \leq \mathbf{C}_i \leq \mathbf{C}$, for all $i$. $1 \leq \mathbf{B}_i \leq 10^9$, for all $i$. (Note that the upper bound only applies to cells that Cody-Jamal already painted. You can assign brightness values larger than $10^9$ to other cells.) - $\mathbf{N} < \mathbf{R} \times \mathbf{C}$. (There is at least one empty cell.) - $\mathbf{R}_i \neq \mathbf{R}_j$ and/or $\mathbf{C}_i \neq \mathbf{C}_j$ for all $i \neq j$. (All of the given cells are different cells in the grid.) **Small dataset (5 Pts, Test Set 1 - Visible)** - Time limit: ~~40~~ 10 seconds. - $1 \leq \mathbf{R} \leq 200$. - $1 \leq \mathbf{C} \leq 200$. **Large dataset (26 Pts, Test Set 2 - Hidden)** - Time limit: ~~80~~ 20 seconds. - $1 \leq \mathbf{R} \leq 10^9$. - $1 \leq \mathbf{C} \leq 10^9$.