题目描述

给出 $R×C$ 的矩阵 $a_{i,j}$。

现需要把矩阵分成 $A×B$ 块 。

先水平地切 $A−1$ 刀（只能切沿整数坐标切）来把划分成 $A$ 块。

然后再把剩下来的每一块独立地切 $B−1$ 刀，也只能切沿整数坐标切。

目标是: 最小的一块的元素和 $S_{min}$ 尽量大。

例如，考虑一个 5×4 的矩阵如下图所示：

1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

若 A=4，B=2，则可以这样切:

1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1

这样，至少能获得 $S_{min}$ 的最大值为 3 。

输入格式

第一行给出四个整数 $R \ C \ A \ B \ (1≤R,C≤500,1≤A≤R,1≤B≤C)$

下来给出R行C列的矩阵$a_{i,j}(a_{i,j} \le 40000)$。

输出格式

输出 $S_{min}$ 的最大值。

输入输出样例 #1

输入 #1

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

输出 #1

3