Treasure Hunt

You are given a grid of size m × n where each cell contains a non-negative integer representing the amount of treasure at that position. Starting from the top-left cell, your goal is to reach the bottom-right cell while collecting as much treasure as possible. At any step, you are allowed to move right, down, or diagonally down-right.

The optimal solution can be determined using dynamic programming. The recurrence relation for the maximum treasure dp[i][j] collected up to cell (i,j) is given by:

[ dp[i][j] = grid[i][j] + \max\begin{cases} dp[i-1][j], \ dp[i][j-1], \ dp[i-1][j-1] \end{cases} ]

Properly handle the boundary cells where some of these options are not available. Your program should read the grid from standard input and output the maximum collected treasure to standard output.

inputFormat

The first line of input contains two space-separated integers m and n, where m is the number of rows and n is the number of columns.

This is followed by m lines, each containing n space-separated integers representing the grid cells.

outputFormat

Output a single integer representing the maximum amount of treasure that can be collected by following the allowed moves.

## sample

3 4
0 2 0 4
1 0 3 1
2 3 4 0

10

</p>