Maximum Coins Collection in a Grid

You are given a grid of size \(m \times n\) where each cell contains an integer representing coins. Some cells may be obstacles, indicated by \(-1\), which you cannot traverse. Starting from the top-left corner at \( (0,0) \), your goal is to move to the bottom-right corner at \( (m-1, n-1) \) by only moving right or down. Each visited cell (if not an obstacle) adds its coin value to your total. If the starting or ending cell is an obstacle or if there is no valid path from start to finish, you should output \(0\).

Note: The coins in each cell (if reachable) are accumulated. If multiple paths exist, choose the one that collects the maximum coins.

inputFormat

The first line contains two integers \(m\) and \(n\) (separated by a space) which represent the number of rows and columns in the grid respectively. The next \(m\) lines each contain \(n\) space-separated integers representing the grid. Cells with a value of \(-1\) are obstacles.

outputFormat

Output a single integer: the maximum number of coins that can be collected along a valid path from the top-left corner to the bottom-right corner. If no valid path exists, output \(0\).

3 4
0 3 1 1
2 0 0 4
1 5 3 1

12