#include #include using namespace std; const int maxn = 1005; int dp[maxn][maxn][2]; int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; vector> mat(n, vector(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> mat[i][j]; } } for(int i = 0; i < n; i++) { int max1 = 0, max2 = 0, idx = 0; for(int j = 0; j < m; j++) { dp[i][j][0] = mat[i][j]; dp[i][j][1] = dp[i][j][0]; dp[1][0][0] = 0; if(i > 0) { dp[i][j][0] += dp[i - 1][j][1]; } if(dp[i][j][0] > max1) { max2 = max1; max1 = dp[i][j][0]; idx = j; } else if(dp[i][j][0] > max2) { max2 = dp[i][j][0]; } } for(int j = 0; j < m; j++) { if(i == 0) { if(j != 0) { dp[0][j][1] += dp[0][0][0]; } } else { if(j == idx) { dp[i][j][1] += max2; } else { dp[i][j][1] += max1; } } } } cout << max(dp[n - 1][m - 1][0], dp[n - 1][m - 1][1]) << endl; return 0; }