/* This works. Mesh approach, mono-directional
     This works     l          j
           -----------------------------------
           |        |          |             |
           |        |          |             |
    i+j-k  -----------------------------------
           |        |       |  |             |
           |        |       |_ |             |
           |        |          |             |
         i -----------------------------------
           |        |          |             |
           |        |          |             |
           -----------------------------------

At time k, 
   s[i][j] is sum of a[i+j-k .. i][1 .. j]
   min[i][j] is minimum of s[i+j-k .. i][1 .. l] for l=1,..,j
   c[i][j] is column sum of a[i+j-k .. i][j]
   max[i][j] is maximum sum of a[i+j-k][l .. j] for l=1,...,j
*/
int a[100][100], c[100][100], s[100][100];
int a1[100][100], c1[100][100], s1[100][100];
int min[100][100]; int max[100][100];
int min1[100][100]; int max1[100][100];
int control[100][100];
int control1[100][100];
int i,k,j,m,n,r; int sol; 
out(int a[100][100]){
int i, j;
for(i=1;i<=n;i++){
  for(j=1;j<=n;j++)printf("%3d",a[i][j]);
  printf("\n");
} }
copyback(int a[100][100], int a1[100][100]){
int i,j;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=a1[i][j];
}
main(){
scanf("%d",&n);
random(); random(); random();
for (i=1;i<=n; i++)
for (j=1;j<=n; j++){
  r=random()%3;
  printf("%d ", r);
  if(r==2)a[i][j]=-1; else a[i][j]=r;
}
printf("\n");
for (i=1;i<=n; i++){
  for (j=1;j<=n; j++) printf("%3d ", a[i][j]);
  printf("\n");
}
for(i=0;i<=n;i++)for(j=0;j<=n;j++)control[i][j]=0;
  for (i=1;i<=n; i++)
    for (j=1;j<=n; j++){
      c[i][0]=0; c[0][j]=0;
      min[i][0]=0; max[i][0]=0;
      control[i][0]=1;
    } 
sol=-99;
for(k=1;k<=2*n-1;k++){
  for (i=1;i<=n; i++)
    for (j=1;j<=n; j++){
      if(control[i][j-1]==1){
      c1[i][j]=c[i-1][j]+a[i][j];
      s1[i][j]=s[i][j-1]+c1[i][j];
      if(s1[i][j]<min[i][j-1])min1[i][j]=s1[i][j]; else min1[i][j]=min[i][j-1];
      if(s1[i][j]-min1[i][j]>max[i][j-1])max1[i][j]=s1[i][j]-min1[i][j]; 
                                  else max1[i][j]=max[i][j-1];
      if(max1[i][j]>sol){
        sol=max1[i][j]; printf("k,i,j,sol= %d %d %d %d",k,i,j,sol); getchar();}
      control1[i][j]=1;
      }
    }
  copyback(s,s1); copyback(c,c1);  copyback(control,control1);
  copyback(min,min1); copyback(max,max1);  
//  getchar(); printf("control=\n"); out(control);
  getchar(); printf("m=\n"); out(min);
  getchar(); printf("s=\n"); out(s);
} /*** k ***/
  printf("sol= %d ",sol);
}