###### tags: `APCS` `c++` `DP`
# 題解 zerojudge f314: 3. 勇者修煉 APCS

#include<bits/stdc++.h>
using namespace std;
int l[10005][55]={0},Ldp[10005][55]={0},Rdp[10005][55]={0},dp[10005][55]={0};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int m,n;
    cin>>m>>n;
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++)   cin>>l[i][j];
    }

    for(int j=1;j<=m;j++){
        for(int x=1;x<=n;x++){
            Ldp[x][j]=max(Ldp[x-1][j],dp[x][j-1])+l[x][j];
        }
        for(int x=n;x>0;x--){
            Rdp[x][j]=max(Rdp[x+1][j],dp[x][j-1])+l[x][j];
            dp[x][j]=max(Ldp[x][j],Rdp[x][j]);
        }
    }
    int ans=-(1e10);
    for(int i=1;i<=n;i++)   ans=max(ans,dp[i][m]);
    cout<<ans<<'\n';
}