小田切蛋糕

题目描述

小田烘培了一块巧克力蛋糕。这块蛋糕是由 $R \times C$ 个小的巧克力蛋糕组成的，第 $i$ 行第 $j$ 列的蛋糕有 $N_{i,j}$ 块巧克力碎屑。

小田想把蛋糕分成 $A \times B$ 块，这样就可以分给 $A \times B$ 只奶牛了。蛋糕会先水平地切 $A-1$ 刀（只能沿整数坐标切）来把蛋糕划分成 $A$ 块。然后再把剩下来地每一块独立地切 $B-1$ 刀，也只能沿整数坐标切。其他 $A \times B - 1$ 只奶牛就每人选一块，留下一块给Bessie 。由于奶牛们都很贪心，它们只会留给 Bessie 巧克力碎屑最少地那块。

请求出 Bessie 在最优情况下可以获得多少巧克力碎屑。

输入描述

第一行输入四个整数 $R,C,A,B$。

接下来 $R$ 行，每行输入 $C$ 个数字 $N_{i,j}$ ，表示对应蛋糕地巧克力碎屑。

输出描述

输出包含一行一个整数，表示最终的答案。

输入输出样例

输入 #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

说明/提示

【样例 1 解释】

如下图这样切：

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

这样，小田能获得 $3$ 块巧克力碎屑。

【数据范围】

对于 $10\%$ 的数据：$A = R,B=C$。

对于另外 $20\%$ 的数据：所有 $N_{i,j}$ 相等。

对于 $100\%$ 的数据：$1 \le R,C \le 500$ ，$1 \le A \le R, 1 \le B \le C$ ，$0\le N_{i,j} \le 4000$ 。