/*** The following program computes the maximum subarray
 a[x1..x1][y2..y1]. The maximum sum is in S
    1  y2 y1                      n
  1 -------------------------------
  x2|  ----                       |
    |  |S |                       |  S is the maximum sum found
  x1|  ----                       |    so far
  z |--------------------------   |
    |       |  s  |  |   t    |   |  t is tentative sum
    |       |     |  |        |   |  s is the maximum found so far
  x |--------------------------   |    in strip from z to x
    |       l     k  j        i   |
    |                             |
  m -------------------------------
************************************************************/
#include <stdio.h>
int i,j,k,l,m,n,x,z,x,x1,x2,y1,y2; 
float s, t, S, w;
float a[100][100];
float column[100][100];
FILE *infile;
main(){
scanf("%d %d",&m,&n); getchar();
// for(i=1;i<=m;i++) for(j=1;j<=n;j++) a[i][j]=random()%100-50;
infile=fopen("gg.dat", "r");
printf("input w "); scanf("%f", &w); getchar();
for(i=1;i<=m;i++) for(j=1;j<=n;j++) fscanf(infile, "%f", &a[i][j]);
for(i=1;i<=m;i++) for(j=1;j<=n;j++) a[i][j]=a[i][j]-w;
printf("Original data\n");
for(i=1;i<=m;i++){
  for(j=1;j<=n;j++) printf("%f ",a[i][j]);
  printf("\n");
}
while(1){
x1=0; x2=0; y1=0; y2=0;
S=-9999;
for(z=1;z<=m;z++){
  for(i=1;i<=n;i++)column[z-1][i]=0;
  for(x=z;x<=m;x++){
    t=0; s=-9999; k=0; l=0;
    j=1; 
    for(i=1;i<=n;i++){
      column[x][i]=column[x-1][i]+a[x][i];
      t=t+column[x][i];
      if(t>s){s=t; k=i; l=j;}
      if(t<0){t=0; j=i+1;}
    } /* i */
    if(s>S){S=s; x1=x; y1=k; x2=z; y2=l;} 
  } /* x */
} /* z */
printf("(x2,y2)=(%d %d), (x1,y1)= (%d %d), S= %f\n", x2,y2,x1,y1,S);
  getchar();
  for(i=x2;i<=x1;i++)for(j=y2;j<=y1;j++)a[i][j]=-9999;
}
}