Description

有N*M的一个非负整数矩阵。现在要把矩阵分成A*B块。矩阵先水平地切A-1刀，把矩阵划分成A块。然后再把剩下来的每一块独立地切竖着B-1刀。每块的价值为块上的数字和。

求一种方案，使得最小价值块的价值最大。

Input Format

第一行四个整数n, m, a, b。

接下来n行，每行m个非负整数。代表这个矩阵

Output Format

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

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

Hint

1<=a<=n<=500

1<=b<=m<=500

其他数字小于4000

Source