分割矩阵

有一个 nxm 的正整数矩阵。 现在要把矩阵分成 axb 块。矩阵先水平地切 a-1 刀，把矩阵划分成 a 块；然后再把剩下来的 每一块独立地切 b-1 刀。每块的价值为块上的数字和。求一种方案，使得最小价值块的价值最大。

输入格式：

第1行，4个整数n、m、a、b。

第n行，每行m个整数，代表这个矩阵。1≤a≤n≤ 500, 1≤b≤m≤500,其他数字小于 4000。

输出格式：

一个数字，最小价值块的价值。

样例：

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