Taco Treasure Hunt

Dora is on a treasure hunt through a rectangular grid. She starts at the top-left cell (0,0) and must reach the bottom-right cell (n-1, m-1) by only moving either to the right or down. Each cell in the grid contains either 0 (no treasure) or 1 (a treasure). Your task is to compute the maximum number of treasures Dora can collect along any valid path.

The problem can be solved using dynamic programming (DP) with the recurrence relation given by:

$$dp[i][j] = \begin{cases} grid[i][j] & \text{if } i = 0 \text{ and } j = 0,\\ dp[i][j-1] + grid[i][j] & \text{if } i = 0,\\ dp[i-1][j] + grid[i][j] & \text{if } j = 0,\\ \max(dp[i-1][j], dp[i][j-1]) + grid[i][j] & \text{otherwise.} \end{cases}$$

Here, \(dp[i][j]\) represents the maximum treasures that can be collected when reaching cell \((i,j)\). The starting cell is \( (0,0) \) and the destination is \( (n-1, m-1) \).

inputFormat

The input is given from stdin in the following format:

The first line contains two space-separated integers (n) and (m), representing the number of rows and columns in the grid respectively.

Each of the next (n) lines contains (m) space-separated integers, where each integer is either 0 or 1, representing the grid cells.

outputFormat

Print to stdout a single integer: the maximum number of treasures Dora can collect on her path.## sample

3 3
1 0 0
0 1 0
0 0 1

3