Two robots work together to collect cherries from grid. They start in the first row, one in the leftmost column and the other in the rightmost column. Each move takes a robot to the next row, either in the same column or one column to the left or right, staying inside the grid. Both robots must reach the last row. They collect cherries from their starting cells and every cell they visit. If both visit the same cell, its cherries count only once. Return the maximum combined total.
Hatched cells show the cells collected by one optimal pair of robot paths.
Example 1:
Input: grid = [[1,2],[3,4]]
Output: 10Explanation: Keep the robots in separate columns on both rows. They collect every cell, for 1 + 2 + 3 + 4 = 10 cherries.
Example 2:
Input: grid = [[0,0,0],[0,5,0]]
Output: 5Explanation: Both robots can move to the middle cell of the last row, but its 5 cherries count only once. The maximum total is 5.
Example 3:
Input: grid = [[5,100,6],[1,1,1]]
Output: 13Explanation: The starting cells provide 5 + 6 cherries. The robots cannot move sideways within the first row to collect its middle 100. On the last row, they can collect two distinct cells for 2 more, giving 13.
Constraints:
2 <= grid.length <= 70- Every row has the same length, between
2and70. 0 <= grid[i][j] <= 100