MS Dhoni is known for his cool nature, however, on many occasions we have seen him lose his calmness when his fielders drop catches. Catches win matches. He has come up with a new activity as a fielding practice for his players, where they can earn points for completing catches.
Players are made to stand in the form of a N * M matrix with values assigned at all positions. If a Player at position (i2, j2) catches a ball from a player standing at (i1, j1), he is rewarded with points equal to the difference of values between the points: (i2, j2) and (i1, j1). Player1 can throw a ball to player2 only if player2 is located either towards right or down in the matrix. Provided that there is only one ball, your task is to determine the maximum reward that can be obtained collectively by the players. The catching can start from any player and can end at any player, and it must include at least two players.
Input Format:
The first line of input consists of two integers N and M denoting the number of rows and columns in the matrix.
The next N lines have M space separated integers denoting the values at each position in the matrix
Output Format:
You need to output the maximum reward that can be obtained by the players
Example 1:
Input: N = 4, M = 4, matrix = [[1, 2, 13, 0], [15, 26, 7, 48], [99, 86, 11, 12], [92, 89, 0, 99]]
Output: 99
Explanation:Maximum reward of 99 can be obtained if the ball is thrown from (3,2) to (3,3),(0,3) to (1,3); score = 48 (1,3) to (2,3); score = -36 (2,3) to (3,3); score = 87 Total score = 99
2 <= N, M <= 1000-1000 <= value(i,j) <=1000
input:
output: