Bessie烘焙了一块巧克力蛋糕。这块蛋糕是由R*C(1 <= R,C <= 500)个小的巧克力蛋糕组成的。 第i行，第j列的蛋糕有N_ij(1 <= N_ij <= 4,000)块巧克力碎屑。 Bessie想把蛋糕分成A*B块，(1 <= A <= R,1 <= B <= C): 给A*B只奶牛。蛋糕先水平地切A-1刀 （只能切沿整数坐标切）来把蛋糕划分成A块。然后再把剩下来的每一块独立地切B-1刀， 也只能切沿整数坐标切。其他A*B-1只奶牛就每人选一块，留下一块给Bessie。由于贪心， 他们只会留给Bessie巧克力碎屑最少的那块。 求出Bessie最优情况下会获得多少巧克力碎屑。 例如，考虑一个5*4的蛋糕，上面的碎屑分布如下图所示： 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕: 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 因此，其他贪得无厌的牛拿完后，Bessie仍能够拿走3个巧克力碎屑。

* 第1行: 四个空格隔开的数: R, C, A ，B * 第2-R+1行: 第i+1行有C个整数, N_i1 , N_i2 .. N_iC

* 第1行: 一个整数: Bessie保证能拿到的最多碎屑数

5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 550

int A,B,n,m,a[N][N],s[N][N],mid;

bool check_row(int x,int y) {

	int i,now=0,sum=0;

	for(i=1;i<=m;i++) {

		if(sum+s[y][i]-s[x-1][i]>=mid) now++,sum=0;

		else sum+=s[y][i]-s[x-1][i];

	}

	return now>=B;

}

bool check() {

	int i,now=0,lst=1;

	for(i=1;i<=n;i++) {

		if(check_row(lst,i)) now++,lst=i+1;

	}

	if(lst<=n) if(check_row(lst,n)) now++;

	return now>=A;

}

int main() {

	scanf("%d%d%d%d",&n,&m,&A,&B);

	int i,l=0,r=0,j;

	for(i=1;i<=n;i++) {

		for(j=1;j<=m;j++) {

			scanf("%d",&a[i][j]);

			s[i][j]=s[i-1][j]+a[i][j];

			r+=a[i][j];

		}

	}

	r++;

	while(l<r) {

		mid=(l+r)>>1;

		if(check()) l=mid+1;

		else r=mid;

	}

	printf("%d\n",l-1);

}