Maximum Gold Path

You are given a grid of non-negative integers representing the amount of gold in each cell. Starting from the top-left cell (0, 0), your goal is to collect as much gold as possible by moving only to the right or down until you reach the bottom-right cell (n-1, m-1).

The value in each cell contributes to the total amount of gold collected when you pass through that cell. Determine the maximum amount of gold that can be collected along a valid path.

Note: The grid will always contain at least one cell.

inputFormat

The first line contains two integers n and m, where n is the number of rows and m is the number of columns in the grid. This is followed by n lines, each containing m space-separated integers representing the gold values in the grid.

outputFormat

Output a single integer — the maximum amount of gold that can be collected along a path from the top-left cell to the bottom-right cell, moving only right or down.## sample

3 3
1 3 1
1 5 1
4 2 1

12