Maximum Reward (Intuit India)

The ball can start from any player and can only be passed right or down in the matrix, and it must pass through at least two players. Each catch earns a reward equal to the value of the receiving cell minus the value of the passing cell. Find the maximum cumulative reward.

输入格式

The input gives N M (2≤N,M≤1000), followed by N lines of M integers each. The source constraints are truncated at the matrix values; this site adds 0≤a[i][j]≤10000. Output the maximum cumulative reward.

输出格式

Output the answer as described; for array answers, separate values with spaces.

样例 1

输入：

4 4
1 2 13 0
15 26 7 48
99 86 11 12
92 89 0 99

输出：

99

样例 2

输入：

2 2
5 1
2 8

输出：

7

样例 3

输入：

2 2
0 4
3 2

输出：

4

样例说明

Scan the matrix, maintaining the minimum value among earlier cells that can reach the current position, and subtract it from the current value.

Correctness: each reward along a path is the later cell minus the earlier cell, so the cumulative sum telescopes to the end minus the start. The start/end pairs reachable by moving monotonically right/down are exactly the pairs of distinct cells whose row and column both do not decrease; for each end, it suffices to subtract the minimum among the reachable earlier cells. Merging the prefix minimums from above and from the left into the current value gives an O(NM) scan.

Complexity: O(NM) time, O(NM) space; the maximum absolute cumulative reward does not exceed 10000.