Collecting Treasures in a Maze

Elara, a brave adventurer, finds herself in a magical maze dotted with treasures. The maze is represented as a 2D grid with dimensions \(n\times m\). Each cell of the grid contains a non-negative integer representing the value of a treasure.

Elara may start at any cell in the first row. From any given cell \((i, j)\), she can only move to one of three cells in the next row: the cell directly below \((i+1,j)\), the cell diagonally to the left \((i+1,j-1)\), or the cell diagonally to the right \((i+1,j+1)\). Her goal is to collect treasures along a path from the top row to the bottom row such that the total collected value is maximized.

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

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

where valid indices are observed.

inputFormat

The input is provided via standard input (stdin) and has the following format:

1. The first line contains two integers \(n\) and \(m\), representing the number of rows and columns respectively.
2. The next \(n\) lines each contain \(m\) space-separated integers, representing the grid of treasure values.

outputFormat

Output a single integer to standard output (stdout) representing the maximum treasure value that Elara can collect by moving from the top row to the bottom row under the allowed movement rules.

3 3
1 3 3
2 1 4
0 6 4

13