Maximum Apples Collection

You are given a grid of size \(n \times m\) where each cell \(matrix[i][j]\) represents the number of apples at that cell. Your task is to start at the top-left cell (cell \((0,0)\)) and move to the bottom-right cell (cell \((n-1, m-1)\)). You can only move either right or down at each step. The goal is to collect the maximum number of apples along the path.

The recurrence relation for this problem is:

\(dp_{i,j} = matrix[i][j] + \max(dp_{i-1,j},\; dp_{i,j-1])\)

with \(dp_{0,0} = matrix[0][0]\) and appropriate handling of the boundaries.

Input/Output

You will be provided with the dimensions of the grid and the grid values. Your program should output the maximum apples that can be collected when moving from the top-left to the bottom-right cell.

inputFormat

The first line of the input contains two integers (n) and (m) (the number of rows and columns of the matrix). Each of the following (n) lines contains (m) integers representing the number of apples in each cell of the matrix.

outputFormat

Output a single integer: the maximum number of apples that can be collected from the top-left corner to the bottom-right corner of the matrix.## sample

3 3
1 2 3
4 5 6
7 8 9

29