1142. Gold Mine Problem — Maximum Gold

Given a mine grid where each cell holds an amount of gold, a miner starts in any row of the first column and moves right, right-up, or right-down each step, collecting gold. Return the maximum gold collectable reaching any column of the last column. The input is JSON {mine}.

Input: JSON {mine}.

Output: Integer — the maximum gold collected.

Examples

Input: {"mine":[[1,3,3],[2,1,4],[0,6,4]]}
Output: 12
Explanation: An optimal diagonal path collects 12.

Input: {"mine":[[1,3,1,5],[2,2,4,1],[5,0,2,3],[0,6,1,2]]}
Output: 16
Explanation: Best path collects 16.

Input: {"mine":[[5]]}
Output: 5
Explanation: Single cell.

Constraints

• 1<=rows,cols<=50

Asked by