Max Magical Items

You are given a grid of integers with n rows and m columns. Each cell in the grid contains a certain number of magical items. Starting from the top-left cell, you can only move either to the right or downward. Your task is to compute the maximum number of magical items that can be collected by the time you reach the bottom-right cell.

The problem can be stated mathematically as follows. Let \(dp[i][j]\) represent the maximum number of magical items that can be collected when arriving at cell \((i,j)\). The recurrence relation is:

[ \begin{aligned} &dp[0][0] = grid[0][0], \ &dp[i][0] = dp[i-1][0] + grid[i][0] \quad (for\ i \ge 1), \ &dp[0][j] = dp[0][j-1] + grid[0][j] \quad (for\ j \ge 1), \ &dp[i][j] = grid[i][j] + \max(dp[i-1][j], dp[i][j-1]) \quad (for\ i, j \ge 1). \end{aligned} ]

Your goal is to output the value of \(dp[n-1][m-1]\).

inputFormat

The input is given from stdin in the following format:

n m
row1_element1 row1_element2 ... row1_elementm
row2_element1 row2_element2 ... row2_elementm
... 
rown_element1 rown_element2 ... rown_elementm

Where:

• n and m (1 ≤ n, m ≤ 1000) are the dimensions of the grid.
• Each of the next n lines contains m integers, representing the number of magical items in each cell.

outputFormat

Output a single integer to stdout -- the maximum number of magical items that can be collected by following the best path.

## sample

3 3
1 2 3
4 5 6
7 8 9

29