#214113. [eJOI 2025] Grid

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

Simona will be placed in cell of a grid of size filled with positive integers. She must reach cell . To do this, she is allowed to repeatedly move from her current cell to any other cell or , such that . For each such move, Simona will receive reward coins , where , are her new coordinates and is a constant cost fixed before the start of the journey. Note that if the expression 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 if and , 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)

• , : the dimensions of the grid;
• : the fixed cost constant for the test;
• : vector of vectors of integers of size , 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 , and .
• lines : integers – the values of .

The output format is the following:

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

样例输入 1

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

样例输出 1

27

样例输入 2

2 2 100
1 2
3 4

样例输出 2

-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 and the number of coins achieved by following it is . Your function must return .

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

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

Constraints

• for and

Subtasks