Taco's Diamond Collection

You are given a grid of size m × n where each cell contains either 0 or 1. Each cell with a 1 represents a diamond. Starting from the top‐left corner, your task is to move to the bottom‐right corner by only moving either right or down, and collect as many diamonds as possible along the way.

The optimal strategy is to use dynamic programming. Define the state as follows:

$$dp_{i,j} = \max(dp_{i-1,j},\; dp_{i,j-1}) + grid_{i,j},$$

with the base cases:

• $$dp_{0,0} = grid_{0,0}$$
• First row: $$dp_{0,j} = dp_{0,j-1} + grid_{0,j}$$
• First column: $$dp_{i,0} = dp_{i-1,0} + grid_{i,0}$$

Print the maximum number of diamonds you can collect, which is the value in the bottom-right cell.

inputFormat

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

This is followed by m lines, each containing n space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer which is the maximum number of diamonds that can be collected along a path from the top-left to the bottom-right corner.

## sample

3 3
0 0 0
0 0 0
0 0 0

0