/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
H 行 W 列からなるマス目があります。
上から i 行目左から j 列目のマスには、A_{i,j}\neq -1 のとき A_{i,j} が書かれており、A_{i,j}=-1 のとき何も書かれていません。
ここで、A_{i,j} は -1 以上 9 以下の整数です。
あなたは、次の条件を満たすように、何も書かれていないマスにそれぞれ 0 以上 9 以下のいずれかの整数を書き込みます。
- 辺を共有するどの 2 マスも、その 2 マスに書かれている数の和が D 以下である
書き込む数の和として考えられる最大値を求めてください。
制約
- 1 \leq H,W \leq 15
- 0 \leq D \leq 18
- -1 \leq A_{i,j} \leq 9
- 入力は全て整数である
- 条件を満たすような書き込み方が存在する
入力
入力は以下の形式で標準入力から与えられる。
H W D
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
出力
答えを出力せよ。
入力例 1
2 3 10 5 -1 3 2 4 -1
出力例 1
11
上から 1 行目・左から 2 列目のマスに 5、上から 2 行目・左から 3 列目のマスに 6 を書き込むと、書き込む数の和は 11 であり、辺を共有するどの 2 マスも和が 10 以下になります。
書き込む数の和を 12 以上にすることはできないため、これが最大です。
入力例 2
2 1 18 -1 0
出力例 2
9
書き込むことができるのは 0 以上 9 以下の整数であることに注意してください。
入力例 3
3 2 10 4 4 4 4 4 4
出力例 3
0
何も書かれていないマスが存在しないこともあります。
入力例 4
8 9 6 2 -1 3 -1 3 2 3 -1 3 -1 2 2 3 -1 3 -1 3 2 -1 3 -1 -1 3 2 3 2 -1 -1 -1 -1 2 2 3 2 -1 2 -1 3 1 -1 -1 2 3 2 2 -1 -1 -1 1 4 1 -1 -1 3 3 -1 -1 4 1 2 -1 -1 2 2 -1 -1 1 -1 -1 2 2 1
出力例 4
91
Problem Statement
There is a grid with H horizontal rows and W vertical columns.
The cell in row i (counted from the top) and column j (from the left) has A_{i,j} written on it if A_{i,j}\neq -1, and is empty if A_{i,j}=-1.
Here, A_{i,j} is an integer between -1 and 9.
You will write an integer between 0 and 9, inclusive, to each empty cell so that:
- For any pair of cells that share a side, the numbers written on the two cells sum to D or less.
Find the maximum possible sum of the numbers newly written.
Constraints
- 1 \leq H,W \leq 15
- 0 \leq D \leq 18
- -1 \leq A_{i,j} \leq 9
- All input values are integers.
- There exists a conforming assignment of numbers.
Input
The input is given from Standard Input in the following format:
H W D
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
Output
Print the answer.
Sample Input 1
2 3 10 5 -1 3 2 4 -1
Sample Output 1
11
By writing 5 to the cell in row 1 and column 2, and 6 to the cell in row 2 and column 3, the newly written numbers sum to 11, and any adjacent cells sum to 10 or less.
This is the maximum, because one cannot make the sum of newly written numbers 12 or greater.
Sample Input 2
2 1 18 -1 0
Sample Output 2
9
Note that we can only write integers between 0 and 9.
Sample Input 3
3 2 10 4 4 4 4 4 4
Sample Output 3
0
There may be no empty cell.
Sample Input 4
8 9 6 2 -1 3 -1 3 2 3 -1 3 -1 2 2 3 -1 3 -1 3 2 -1 3 -1 -1 3 2 3 2 -1 -1 -1 -1 2 2 3 2 -1 2 -1 3 1 -1 -1 2 3 2 2 -1 -1 -1 1 4 1 -1 -1 3 3 -1 -1 4 1 2 -1 -1 2 2 -1 -1 1 -1 -1 2 2 1
Sample Output 4
91