Taco Grid Maximum Coins

You are given a grid filled with non-negative integers representing coins. Your task is to determine the maximum number of coins that can be collected by starting at the top-left corner and reaching the bottom-right corner, while only moving right or down at any step.

Formally, given a grid \(G\) of dimensions \(m \times n\), find the maximum sum along a path from \(G_{0,0}\) to \(G_{m-1,n-1}\) using only rightward and downward moves.

inputFormat

The input is read from stdin. The first line contains two integers m and n, representing the number of rows and columns respectively. The following m lines each contain n space-separated integers that represent the coins in the grid.

outputFormat

Output a single integer which is 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 is printed to stdout.## sample

3 3
1 3 1
1 5 1
4 2 1

12