Maximum Apples Collection

Alice is traversing an orchard represented by an n x m grid where each cell contains a certain number of apples. She starts at the top-left cell (1, 1) and aims to reach the bottom-right cell (n, m), moving only right or down at each step. As she moves, she collects the apples in each cell. Your task is to help Alice determine the maximum number of apples she can collect.

The recurrence used is given by the formula: \[ dp[i][j] = grid[i][j] + \max\begin{cases} dp[i-1][j] & \text{if } i > 0 \\ dp[i][j-1] & \text{if } j > 0 \end{cases} \] with the initialization \(dp[0][0] = grid[0][0]\).

inputFormat

The first line contains two integers n and m (the number of rows and columns respectively). The following n lines each contain m integers, representing the grid where each integer denotes the number of apples at that cell.

outputFormat

Output a single integer, which is the maximum number of apples Alice can collect when traveling from the top-left to the bottom-right of the grid.

3 3
1 2 3
4 5 6
7 8 9

29