Slingshot ~ WildLife-TK

You are given a

$N \times M$ matrix $A$ , filled with distinct numbers. You can start at any cell. If you are currently at cell $(x_{1}, y_{1})$ , then you can jump to any other cell $(x_{2}, y_{2})$ , if and only if the following two conditions are satisfied:

$A_{x_{2}, y_{2}} > A_{x_{1}, y_{1}}$
Manhattan distance between $A_{x_{2}, y_{2}}$ and $A_{x_{1}, y_{1}}$ $> S$ . Formally, $| x_{1} - x_{2} | + | y_{1} - y_{2} | > S$ .

Let $V$ be the set of the cells visited by you.

Maximize the value of $\sum_{(x, y) \in V} A_{x, y}$ .

Input Format

The first line of the input contains the number $T$ - the number of test cases. Then the test cases follow.
The first line of each test case contains three integers $N, M, S$ - the parameters defined in the statement.
Then $N$ lines follow, with $M$ integers in each line.
Each of the next $N$ lines contains $M$ integers, where the $j$ -th integer in $i$ -th line is equal to $A_{i, j}$

Output Format

For each testcase output the maximum possible value of $\sum_{(x, y) \in V} A_{x, y}$ .

Constraints

$1 \leq N, M \leq 1000$
$0 \leq S \leq N + M - 2$ .
$1 \leq A_{i, j} \leq 10^{9}$ .
It's guaranteed that all $A_{i, j}$ are distinct.
It's guaranteed that sum of $N \times M$ over all test cases doesn't exceed $10^{6}$ .

Sample Input 1

Sample Output 1

9
394

Explanation

Test case-1: It is optimal start at cell $(1, 1)$ , then jump to cell $(3, 2)$ . Therefore answer is $A_{1, 1} + A_{3, 2} = 1 + 8 = 9$ .

Test case-2: It is optimal to start at $(2, 2)$ and follow this path: $(2, 2) \to (2, 1) \to (1, 2) \to (1, 1)$ . Therefore answer is the sum of all the four cells $= 394$ .

Slingshot