1100. Cherry Pickup II — Two Robots

Given a grid where grid[r][c] is the number of cherries in a cell, two robots start at the top-left and top-right corners. Each moves down one row per step to an adjacent column (down-left, down, or down-right). They collect cherries on visited cells (a shared cell counts once). Return the maximum cherries the two robots can collect together reaching the bottom row. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the maximum cherries collected.

Examples

Input: {"grid":[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]}
Output: 24
Explanation: Optimal joint collection.

Input: {"grid":[[1,1],[1,1]]}
Output: 4
Explanation: Robots cover all four cells.

Input: {"grid":[[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]}
Output: 28
Explanation: Best paths for both robots.

Constraints

• 1<=rows<=70
• 2<=cols<=70

Asked by