Max Magic Crystals

A brave wizard embarks on a journey through a mystical grid to collect as many magic crystals as possible. The wizard starts at the top-left cell of the grid and aims to reach the bottom-right cell. At each step, the wizard can only move either right or down.

The grid is represented as a matrix of non-negative integers, where each integer represents the number of magic crystals available in that cell. The objective is to maximize the total number of crystals collected along the path from the starting cell to the destination.

Formally, given an n×m grid \(G\), define a function \(dp(i,j)\) as the maximum crystals collectible when arriving at cell \((i,j)\). The recurrence is given by:

[ \begin{aligned} dp(i,j) &= G(i,j) + \max\big( dp(i-1,j),, dp(i,j-1) \big), \quad \text{for } i>0, \ j>0, \ dp(0,j) &= G(0,j) + dp(0,j-1), \quad j>0, \ dp(i,0) &= G(i,0) + dp(i-1,0), \quad i>0, \ dp(0,0) &= G(0,0). \end{aligned} ]

Your task is to implement a program that reads the grid from standard input and outputs the maximum number of magic crystals the wizard can collect when traversing from the top-left to the bottom-right cell.

inputFormat

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

This is followed by n lines, each containing m space-separated integers. Each integer represents the number of magic crystals in that cell.

outputFormat

Output a single integer, which is the maximum number of magic crystals that can be collected when traversing from the top-left corner to the bottom-right corner of the grid.

3 3
1 3 1
1 5 1
4 2 1

12