P7074

#include <bits/stdc++.h>
using namespace std;
int a[100][100],utd[10010],dtu[10010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];

		}
	}
	for(int i=2;i<=n;i++)
	{
		a[i][1]+=a[i-1][1];
	}
	cout<<endl;
	for(int i=2;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(j==1)utd[j]=a[j][i-1]+a[j][i];
			else utd[j]=max(utd[j-1]+a[j][i],a[j][i]+a[j][i-1]);				
		}
		for(int j=n;j>=0;j--)
		{
			if(j==n)dtu[j]=a[j][i-1]+a[j][i];
			else dtu[j]=max(dtu[j+1]+a[j][i],a[j][i]+a[j][i-1]);				
		}
		for(int j=1;j<=n;j++)
		{
			a[j][i]=max(dtu[j],utd[j]);
		}
	}
	cout<<a[n][m];
	return 0;
}