class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size(),m = grid[0].size();
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(m + 2, vector<int>(m + 2)));
        for(int i=n-1;i>=0;i--){
            //哪怕左上角的机器人一直往右下走，j也不会超过i，最多就相等，所以j>i的情况都不存在
            for(int j=0;j<min(m,i+1);j++){
                //哪怕右上角的机器人一直往左下走，k也不会超过m-i-1，最多就相等，所以这种情况都不存在
                //并且两机器人线路交叉也没意义，如果穿过去能更多，那更近的机器人应该自己走那条路，所以k>j
                for(int k=max(j+1,m-1-i);k<m;k++){
                    //九种情况取max:[j...j+2] × [k...k+2]
                    f[i][j+1][k+1] = max({
                        f[i + 1][j][k], f[i + 1][j][k + 1], f[i + 1][j][k + 2],
                        f[i + 1][j + 1][k], f[i + 1][j + 1][k + 1], f[i + 1][j + 1][k + 2],
                        f[i + 1][j + 2][k], f[i + 1][j + 2][k + 1], f[i + 1][j + 2][k + 2]
                    }) + grid[i][j] + grid[i][k];
                }
            }
        }
        return f[0][1][m];
    }
};