2909: 分割矩阵
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
有N*M的一个非负整数矩阵。现在要把矩阵分成A*B块。矩阵先水平地切A-1刀，把矩阵划分成A块。然后再把剩下来的每一块独立地切竖着B-1刀。每块的价值为块上的数字和。求一种方案，使得最小价值块的价值最大。
输入
第一行四个整数N,M,A,B。
接下来N行，每行M个非负整数。代表这个矩阵。
输出
一个数字。最小价值块的价值。
样例输入 复制
5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1样例输出 复制
3提示
【样例解释】
1 2 | 2 1
----------
3 | 1 1 1
----------
2 0 1 | 3
----------
1 1 | 1 1
1 1 | 1 1
【数据规模】
1<=A<=N<=500
1<=B<=M<=500
其他数字小于4000。