Maximum Gold Collection

You are given a grid with \(R\) rows and \(C\) columns. Each cell in the grid contains a non-negative integer representing the amount of gold in that cell. You may start from any cell that contains a non-zero amount of gold and you can move in four directions: up, down, left, and right. However, you cannot visit the same cell more than once during your journey.

Your task is to determine the maximum amount of gold that can be collected by following a valid path. More formally, given a grid \(G\) of size \(R \times C\), find the maximum sum obtainable by traversing adjacent cells (vertically or horizontally) without revisiting any cell.

Note: The path can start at any cell containing a non-zero value and stops when there are no adjacent cells with non-zero gold.

inputFormat

The first line contains two integers \(R\) and \(C\) indicating the number of rows and columns in the grid, respectively.

Each of the following \(R\) lines contains \(C\) space-separated integers representing the amount of gold in each cell.

outputFormat

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

4 3
1 0 7
2 0 6
3 4 5
0 3 0

28