/*
习题 95：恶魔岛救公主(3)★★★★★(Contest 12)
题目描述：
Goldfisher为了解救被绑架的未婚妻而来到了恶魔岛。
上岛前，一个神秘的印度人Yingnan告诉他恶魔岛处处布满陷阱，
给Goldfisher画了一个草图，如一个4*4的房间布局如下：
1 6 2 4
2 3 1 2
1 5 9 3
9 1 2 1
每前进一步，只能选择进入上下左右任一房间。
而Goldfisher首先将站在左上方的格子，
数字表示那个房间里藏着的魔法豆的数目，
Goldfisher每进入一个房间就要把那个房间里的所有魔法豆取走。
而他的未婚妻就在最右下方的房间中。
Goldfisher必须以最短的路线救走他的未婚妻并返回出发点，
并把他手上所有的魔法豆倒进时空机器，当有足够多的魔法豆，
时空机才会送他们回去。这时Goldfisher犯难了，
因为他不知道需要多少魔法豆才足够，所以希望尽可能多拿，
但问题又必须以最短的路线，否则被敌人发现的话，
就连自己也逃不掉了。他希望找出这样一条路线，
尽可能地短，并且能尽可能多取得魔法豆。
如上图应该走1-6-3-5-9-3-1(返回)-2-1-9-1-2-1
一共有1+6+3+5+9+3+1+2+1+9+1+2=43个魔法豆。
你能帮助Goldfisher找到正确的道路解救他的未婚妻吗？
输入：
有多个测试，每个测试第一行分别是两个整数m,n(2<=m,n<=100)，
接下来的m行n列按顺序地描述了这个地图上相应房间里的魔法豆的数目。
数目在0到10000之间（包括两端）。
最后当输入的m=n=0表示结束。
输出：
对于每个测试，输出当路线最短时，
最多可以得到的魔法豆的数目
样例输入：
4 4
1 6 2 4
2 3 1 2
1 5 9 3
9 1 2 1
3 4
0 1 1 0
1 0 1 0
0 1 1 0
0 0
样例输出：
43
6
其它信息：
难度：Very Difficult
*/
#include<stdio.h>
#include<string.h>
int map[256][256];
int d[2][256][256];
/* 阶段,X1,X2 */
int max(int a,int b)
{
return a>b ? a : b;
}
int min(int a,int b)
{
return a>b ? b : a;
}
int main(void)
{
int m,n;
int t;
int x;
int i,j,k;
int *dst,*src,*temp;
dst=&d[0][0][0];
src=&d[1][0][0];
while(1)
{
scanf("%d%d",&m,&n);
if(m==0 && n==0) break;
x=m+n-1;
t=max(m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
memset(d,0,sizeof(d));
for(i=1;i<=x;i++) /*i:阶段*/
{
temp=dst; dst=src; src=temp;
for(j=1;j<=min(i,n);j++) /* X1 */
for(k=1;k<=j;k++) /* X2 */
{
dst[j*256+k]=max(max(src[(j-1)*256+k-1],src[j*256+k-1]),
max(src[(j-1)*256+k],src[j*256+k]));
if(j==k) dst[j*256+k]+=map[i-k+1][k];
else dst[j*256+k]+=map[i-j+1][j]+map[i-k+1][k];
}
}
printf("%d\n",dst[n*256+n]);
}
return 0;
}