Maximum Sum Path in a Matrix

Given an n x m matrix of integers, find the maximum sum path from the top-left corner to the bottom-right corner. At each step, you can move to the right, down, or diagonally down-right.

The recurrence relation for the dynamic programming solution is given by:

$$dp[i][j] = matrix[i][j] + \max(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1])$$

You are required to read the matrix from standard input where the first line contains two integers n and m (the number of rows and columns, respectively), followed by n lines each containing m integers. Then, compute and output the maximum sum collected on a path following the allowed moves.

inputFormat

The input is read from standard input and is formatted as follows:

• The first line contains two integers n and m separated by a space.
• The next n lines each contain m integers separated by spaces, representing the matrix.

outputFormat

Output a single integer which is the maximum sum path from the top-left corner to the bottom-right corner.

3 3
1 2 3
4 5 6
7 8 9

29