问题 I: 分割矩阵

问题 I: 分割矩阵

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

 有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。


[提交][状态]