Maximum Treasure Collection

You are given a grid of size \(N \times M\) where each cell contains a non-negative integer representing the treasure amount. Starting from the top-left cell (1,1), your goal is to reach the bottom-right cell (N,M) while collecting as much treasure as possible. You are allowed to move in three directions: right, down, or diagonally down-right. Formally, if you are at cell \((i, j)\), you may move to \((i, j+1)\), \((i+1, j)\), or \((i+1, j+1)\).

If there is no valid path (for example, when there are zero rows or zero columns), the answer should be 0.

Note: All moves add the treasure value of the destination cell to your total. Your task is to compute the maximum amount of treasure that can be collected following these movement rules.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (N) and (M) separated by a space. Each of the next (N) lines contains (M) space-separated integers representing the grid.

outputFormat

Print to standard output (stdout) a single integer representing the maximum treasure that can be collected.## sample

3 3
1 2 3
4 5 6
7 8 9

29