E. Grid Walking+
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an $$$n*m$$$ grid.There's an integer $$$a_{i,j}$$$ in $$$(i,j)$$$.

Here're some rules:

  1. You can start from any cell,and end at any cell;

  2. In one move,you can move left,right or down(but not move up or beyond the boundary);

  3. Each move will incur a cost of $$$c$$$;

  4. You can access the same cell multiple times.

Note $$$S$$$ as the set of cells you have accessed,and $$$k$$$ as your number of moves.Your score is defined as $$$\Sigma_{(i,j)∈S}a_{i,j}-kc$$$.

Find the maximum value of your score.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 1000)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line contains three integers $$$n,m,c(1 \leq n,m \leq 2000,1 \leq c \leq 10^9)$$$.

The next $$$n$$$ lines describe $$$a$$$.The next $$$i$$$ line contains $$$m$$$ integers $$$a_{i,1},a_{i,2},...,a_{i,m}(-10^9 \leq a_{i,j} \leq 10^9)$$$.

The sum of $$$n,m$$$ over all test cases will not exceed $$$2000$$$.

Output

For each test case, output an integer on a new line — the maximum value of your score.

Example
Input
4
3 3 1
-2 -2 -2
-2 -1 -2
-2 -2 -2
4 5 2
-1 9 9 -1 -1
-2 0 9 -2 -1
9 -1 9 -1 -2
0 -1 -2 9 -2
6 5 3
-2 -3 3 9 6
8 7 5 -1 -1
-1 1 1 7 7
-4 -6 6 4 5
9 9 8 5 9
9 -9 6 5 7
6 6 1
8 3 -6 4 4 5
3 -9 -2 4 -1 -9
-1 -9 2 -3 -8 5
-8 -2 -6 -8 -7 -8
-5 3 -5 3 7 1
-9 5 -3 4 2 7
Output
-1
34
58
19
Note

Test case $$$1$$$:

Just start from $$$(2,2)$$$ and end at $$$(2,2)$$$.Your score is $$$a_{2,2}=-1$$$.

Test case $$$2$$$:

$$$(1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,2) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (4,4)$$$

Your number of moves $$$k=9$$$.Your score is $$$a_{1,2}+a_{1,3}+a_{2,3}+a_{3,1}+a_{3,2}+a_{3,3}+a_{3,4}+a_{4,4}-kc=9+9+9+9-1+9-1+9-9*2=34$$$.