题目描述

Simona dreams of uncountable riches. She is offered to play a game for a big prize.

Simona will be placed in cell $(0, 0)$ of a grid $A$ of size $N \times M$ filled with positive integers. She must reach cell $(N-1, M-1)$. To do this, she is allowed to repeatedly move from her current cell $(x, y)$ to any other cell $(x + d, y)$ or $(x, y + d)$, such that $d > 0$. For each such move, Simona will receive reward coins $|A_{x,y} - A_{x',y'}| - C$, where $x'$, $y'$ are her new coordinates and $C$ is a constant cost fixed before the start of the journey. Note that if the expression $|A_{x,y} - A_{x',y'}| - C$ evaluates to a negative number, Simona will lose coins. Note also that it is possible to end the game with a negative number of coins.

Help Simona determine the maximum number of coins she can finish the game with.

Note that $|a| = a$ if $a \geq 0$ and $|a| = -a$, otherwise.

Implementation details

You have to implement the function max_profit:

long long max_profit(int N, int M, int C, std::vector<std::vector<int>> A)

• $N$, $M$: the dimensions of the grid;
• $C$: the fixed cost constant for the test;
• $A$: vector of vectors of integers of size $N \times M$, representing the two dimensional grid (indexed by row and then column).

This function will be called once for each test and has to return the maximum number of coins Simona can end the game with.

输入格式

The input format is the following:

• line 1: three integers – the values of $N$, $M$ and $C$.
• lines $2 - (N + 1)$: $M$ integers – the values of $A_{i,j}$.

输出格式

The output format is the following:

• line 1: one integer – the return value of the call.

5 6 4
20 24 31 33 36 40
25 23 25 31 32 39
31 26 21 24 31 35
32 28 25 21 26 28
36 35 28 24 21 27

27

2 2 100
1 2
3 4

-197

提示

Example

Consider the following call:

max_profit(5, 6, 4, {{20, 24, 31, 33, 36, 40},
{25, 23, 25, 31, 32, 39},
{31, 26, 21, 24, 31, 35},
{32, 28, 25, 21, 26, 28},
{36, 35, 28, 24, 21, 27}})

In this case the optimal path is $(0,0) \xrightarrow{7} (0,2) \xrightarrow{2} (1,2) \xrightarrow{10} (1,5) \xrightarrow{8} (4,5)$ and the number of coins achieved by following it is $7 + 2 + 10 + 8 = 27$. Your function must return $27$.

max_profit(2, 2, 100, {{1, 2}, {3, 4}})

Here your function must return: $-197$. Note that the answer may be negative value.

Constraints

• $1 \leq N, M$
• $N \cdot M \leq 500000$
• $1 \leq A_{i,j} \leq 1000000$ for $0 \leq i < N$ and $0 \leq j < M$
• $0 \leq C \leq 1000000$

Subtasks

Subtask	Points	Required subtasks	Additional constraints
0	$0$	-	The example.
1	$9$		$N = 1, M \leq 200$
2	$5$		$N = 1, A_{i,j} \leq A_{i,j+1}$
3	$8$		$N = 1, C = 0$
4	$10$	$1$	$N = 1, M \leq 50000$
5	$7$	$1-4$	$N = 1$
6	$15$	$1$	$N, M \leq 200$
7	$9$	$2$	$A_{i,j} \leq A_{i+1,j}, A_{i,j+1}$
8	$12$	$3$	$C = 0$
9		$0-1, 4, 6$	$N \cdot M \leq 50000$
10	$13$	$0-9$	-