Maximum Coins in a Grid

You are given a grid with ( n ) rows and ( m ) columns. Each cell of the grid contains a certain number of coins. Starting from the top-left cell, your task is to reach the bottom-right cell while collecting as many coins as possible. At each step, you may only move either right or down.

The DP recurrence for this problem is given by: [ \text{dp}[i][j] = \text{grid}_{ij} + \max(\text{dp}[i-1][j],, \text{dp}[i][j-1]) ]

Your goal is to compute ( \text{dp}[n-1][m-1] ), the maximum number of coins that can be collected along a valid path.

inputFormat

Input is read from standard input (stdin). The first line contains two integers ( n ) and ( m ) separated by a space, representing the number of rows and columns respectively. The following ( n ) lines each contain ( m ) integers separated by spaces, representing the grid row by row.

outputFormat

Output the maximum number of coins that can be collected on a valid path from the top-left corner to the bottom-right corner. The output should be printed to standard output (stdout).## sample

3 3
1 3 1
1 5 1
4 2 1

12