Simona 梦想着数不尽的财富。她被邀请参加一个可以获得丰厚奖品的网格游戏。
Simona 将被放置在一个大小为 $N \times M$ 且填满正整数的网格 $A$ 的单元格 $(0, 0)$ 中。她必须到达单元格 $(N - 1, M - 1)$。为此，她可以重复地从当前单元格 $(x, y)$ 移动到任何其他单元格 $(x + d, y)$ 或 $(x, y + d)$，其中 $d > 0$。对于每一次这样的移动，Simona 将获得 $|A_{x,y} - A_{x',y'}| - C$ 个金币的奖励，其中 $x', y'$ 是她的新坐标，$C$ 是在旅程开始前确定的常数花费。请注意，如果表达式 $|A_{x,y} - A_{x',y'}| - C$ 的值为负数，Simona 将失去金币。还要注意，游戏结束时金币数量可能为负数。
帮助 Simona 确定她结束游戏时能获得的最多金币数量。
注意，若 $a \ge 0$ 则 $|a| = a$，否则 $|a| = -a$。
实现细节
你需要实现函数 max_profit：
long long max_profit(int N, int M, int C, std::vector<std::vector<int>> A)N,M：网格的维度；C：测试点固定的花费常数；A：大小为 $N \times M$ 的二维整型vector，表示二维网格（以行和列为索引）。
该函数在每个测试点中会被调用一次，且必须返回 Simona 结束游戏时能获得的最多金币数量。
数据范围
- $1 \le N, M$
- $N \cdot M \le 500\,000$
- $1 \le A_{i,j} \le 1\,000\,000$ 对于 $0 \le i < N$ 且 $0 \le j < M$
- $0 \le C \le 1\,000\,000$
子任务
| 子任务 | 分值 | 依赖子任务 | 附加限制 |
|---|---|---|---|
| 0 | 0 | — | 样例 |
| 1 | 9 | — | $N = 1, M \le 200$ |
| 2 | 5 | — | $N = 1, A_{i,j} \le A_{i,j+1}$ |
| 3 | 8 | — | $N = 1, C = 0$ |
| 4 | 10 | 1 | $N = 1, M \le 50\,000$ |
| 5 | 7 | 1 - 4 | $N = 1$ |
| 6 | 15 | 1 | $N, M \le 200$ |
| 7 | 9 | 2 | $A_{i,j} \le A_{i+1,j}, A_{i,j+1}$ |
| 8 | 12 | 3 | $C = 0$ |
| 9 | 12 | 0 - 1, 4, 6 | $N \cdot M \le 50\,000$ |
| 10 | 13 | 0 - 9 | 无 |
样例评测程序
输入格式如下：
- 第 1 行：三个整数，分别表示 $N, M$ 和 $C$ 的值。
- 第 $2$ 至 $N + 1$ 行：每行 $M$ 个整数，表示 $A_{i,j}$ 的值。
输出格式如下：
- 第 1 行：一个整数，表示函数调用的返回值。
样例
输入样例 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
说明 1
对于第一组样例，对应的函数调用为：
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}})
在这种情况下，最优路径为 $(0, 0) \xrightarrow{7} (0, 2) \xrightarrow{2} (1, 2) \xrightarrow{10} (1, 5) \xrightarrow{8} (4, 5)$，沿着该路径获得的金币数量为 $7 + 2 + 10 + 8 = 27$。函数必须返回 27。
输入样例 2
2 2 100 1 2 3 4
输出样例 2
-197
说明 2
对于第二组样例，对应的函数调用为：
max_profit(2, 2, 100, {{1, 2}, {3, 4}})
在这种情况下，函数必须返回 -197。请注意，答案可能为负数。