#include<vector>

#include<algorithm>

classSolution {

intcherryPickup(vector<vector<int>>& grid) {

int rows = grid.size();

int cols = grid[0].size();

vector<vector<vector<int>>>dp(rows, vector<vector<int>>(cols, vector<int>(cols,0)));

for (int i = rows -1; i >=0; --i) {

for (int j =0; j < cols; ++j) {

for (int k =0; k < cols; ++k) {

int cherries = grid[i][j] + (j != k ? grid[i][k] :0);

if (i == rows -1) {

dp[i][j][k] = cherries;

}else {

int maxCherries =0;

for (int dj = -1; dj <=1; ++dj) {

for (int dk = -1; dk <=1; ++dk) {

int nj = j + dj;

int nk = k + dk;

if (nj >=0 && nj < cols && nk >=0 && nk < cols) {

maxCherries =max(maxCherries, dp[i +1][nj][nk]);

}

}

}

dp[i][j][k] = cherries + maxCherries;

}

}

}

}

return dp[0][0][cols -1];

}

};