题目描述

给出一个 $n$ 行 $m$ 列的矩阵。你可以横着切 $r$ 刀，竖着切 $s$ 刀将它分成小的矩阵。现在希望每个小矩阵的总和，最大的那个最小化。

输入格式

第一行给出 $n, m, r, s$。

下面 $n$ 行 $m$ 列给出矩阵。

输出格式

总和最大的那个矩阵，其值最小可以为多少。

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

31

样例说明

从第二行、第四行下边、第四列右边把矩阵切开，所得的六个矩阵的和分别为 $21, 13, 27,27, 17, 31$。可以证明没有比 $31$ 更小的答案。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n, m \le 18, s \le n, t \le m$。