1253. Cherry Pickup II — Two Robots

Two robots start at the top-left and top-right cells of a grid of cherry counts. Each moves down one row per step, shifting by -1, 0, or +1 column, until both reach the bottom row. They collect the cherries in the cells they occupy, and a cell shared by both robots is counted once. Return the maximum cherries collected. 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: The robots take complementary paths.

Input: {"grid":[[1,1],[1,1]]}
Output: 4
Explanation: Both robots collect their columns.

Input: {"grid":[[5]]}
Output: 5
Explanation: Both robots share the single cell.

Constraints

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

Asked by