407016: GYM102687 C Forklifter

After the completion of his manga Tights in The Wind, mangaka Kakushi Gotou took a part time job as a JUMP! comics warehouse forklifter.

The warehouse is a parallelogram with row length $$$r$$$ and column length $$$c$$$. The storage slots of the warehouse are mini hexagons denoted by coordinates $$$(i,j)$$$, where $$$i$$$ is its row number and $$$j$$$ is its column number. The slot at coordinate $$$(i,j)$$$ has $$$A_{(i,j)}$$$ JUMP! comics already stacked on it.

We define the instability of the warehouse stacks to be the largest difference in height between any two adjacent storage slots in the warehouse. We say two stacks are adjacent if their hexagonal slots share a side. More formally, the slot at coordinate $$$(i,j)$$$ is adjacent to the slots at coordinates $$$(i,j-1)$$$, $$$(i,j+1)$$$, $$$(i-1,j)$$$, $$$(i-1,j+1)$$$, $$$(i+1,j-1)$$$, and $$$(i+1,j)$$$ (if they exist). The arrows in the above grid visually depict adjacent nodes.

Kakushi's job is to minimize this instability in order to prevent a potential book avalanche. To do so, he can bring in up to $$$k$$$ JUMP! comics, which he can pile up on any stack he wishes. To avoid garnering hatred from his forklifter senpais, Kakushi does not want to move comics initially/already stacked in the warehouse.

What is the minimum instability of the warehouse if Kakushi brings in the optimal number of JUMP! comics and places them on the stacks optimally?

Note: The warehouse grid is NOT a rectangle, it is a slanted parallelogram. Look at the sample input/output explanation or the above warehouse grid example for clarity.

The first line of input contains $$$t$$$, the number of test cases.

Each test case begins with three integers $$$r$$$, $$$c$$$, and $$$k$$$, the number of rows of the warehouse, the number of columns of the warehouse, and the maximum number of comics Kakushi can bring in, respectively.

$$$r$$$ lines then follow, each containing $$$c$$$ integers. The $$$j$$$th integer in the $$$i$$$th line denotes the number of comics at coordinate $$$(i,j)$$$, i.e. $$$A_{(i,j)}$$$.

Output one integer, the minimum instability obtainable by placing up to $$$k$$$ JUMP! comics in the warehouse stacks.

For all subtasks

$$$1 \le A_{(i,j)} \le 10^{12}$$$

$$$0 \le k \le 10^{18}$$$

$$$1 \le r, c, rc \le 10^5$$$

The sum of the $$$rc$$$'s in a single file is $$$\le 4\cdot 10^5$$$

$$$1 \le t \le 10$$$

$$$rc > 1$$$

Subtask 1 (5 points):

$$$k = 0$$$

Subtask 2 (10 points):

$$$r, c, rc, k \le 200$$$

Subtask 3 (15 points):

$$$r, c, rc \le 200$$$

Subtask 4 (15 points):

$$$r, c, rc \le 3000$$$

Subtask 5 (20 points):

$$$r = 1$$$ or $$$c = 1$$$

Subtask 6 (20 points):

$$$rc \le 30000$$$

The sum of the $$$rc$$$'s in a single file is $$$\le 60000$$$

Subtask 7 (15 points):

No additional constraints.

1
3 5 12
15 13 9 13 9
11 5 11 13 12
10 13 8 16 16

4

Note: The sample case is not valid for the first and fifth subtasks. It is valid for the other subtasks.

The warehouse has $$$r=3$$$ rows and $$$c=5$$$ columns. Kakushi can bring in up to $$$k=12$$$ JUMP! comics. The warehouse initially looks like the following:

Kakushi can choose to bring in $$$11$$$ comics to the warehouse and place them as follows:

This way, the maximum difference between any two adjacent cells in the grid is $$$4$$$, and exactly $$$11$$$ comics are used.