Maximum Gold Path

You are given a 2D grid where each cell contains a non-negative integer representing the amount of gold in that cell. You can start your journey from any cell with a positive amount of gold.

You can move in any of the four cardinal directions (up, down, left, or right) from the current cell. However, you cannot visit the same cell more than once in a single journey.

Your task is to determine the maximum amount of gold you can collect by starting from some cell and moving through the grid according to the rules above.

In mathematical terms, given a grid with dimensions \(R \times C\), where the element \(g_{i,j}\) represents the gold in the cell at row \(i\) and column \(j\), find the maximum sum of gold collected along any valid path.

inputFormat

The first line contains two space-separated integers \(R\) and \(C\) representing the number of rows and columns in the grid.

Each of the next \(R\) lines contains \(C\) space-separated integers, where each integer represents the gold amount in that cell.

outputFormat

Output a single integer: the maximum gold that can be collected.

3 3
0 6 0
5 8 7
0 9 0

24