Maximum Path Sum in an Increasing Grid

You are given an \(n \times m\) grid where each cell contains an integer. You can start from any cell and move to an adjacent cell (up, down, left, or right) as long as the adjacent cell's number is strictly greater than the current cell's number. Your task is to plan a path such that the sum of all numbers on the path is maximized.

Note: Moves are only allowed to cells sharing an edge, and you cannot move outside the grid.

The problem can be formulated as finding the maximum sum path with the constraint that if the current cell is \(a_{ij}\) and you move to an adjacent cell \(a_{kl}\), then \(a_{kl} > a_{ij}\).

inputFormat

The first line of input contains two integers \(n\) and \(m\) (1 ≤ n, m ≤ 1000) representing the number of rows and columns in the grid.

Each of the next \(n\) lines contains \(m\) integers, representing the grid. Each integer is the value in that cell.

outputFormat

Output a single integer representing the maximum possible sum of numbers along any valid path.

sample

1 1
5

5