题目描述

题目译自 BalticOI 2008 Day2「Grid」

Byteland 国的地图是一个大小为 $n\times m$ 的网格（$n$ 是垂直方向长度，$m$ 是水平方向长度）。标记分隔的水平线被叫做平行线，并编号为 $0$ 到 $n$，标记分隔的垂直线被叫做子午线，并编号为 $0$ 到 $m$。
在 Byteland 国，天气预报是一个十分严肃的话题，对于每个单元格，准备天气预报需要一定时间来计算。由于地形条件和其他因素，不同的单元格有着不同的计算时间。直到目前为止，预报系统还是会依次处理每一个单元格，所以完成预报天气需要花费的时间为计算所有单元的时间。

你被要求设计一个可以在多进程处理器上运行的新系统，为了共享处理器的计算能力，Byteland 国要被 $r$ 条平行线和 $s$ 条子午线划分为 $(r+1)(s+1)$ 个矩形。每个线程会依次处理一个矩形内部的单元格，这样的话对于一个矩形区域的计算时间，就为矩形区域内单元格计算时间之和。完成预报的计算时间是一个处理器上计算时间的最大值。
你的任务是找到对于选择 $r$ 条平行线和 $s$ 条子午线分隔后最小的计算时间。

任务

写一个程序能够：

• 从标准输入读取 Byteland 的地图，要求的平行线和子午线条数以及每个单元格的处理时间；
• 找到完成预报的最小计算时间；
• 输出这个值到标准输出。

输入格式

第一行包含四个正整数 $n,m,r,s$，由一个空格隔开。
接下来 $n$ 行包含每一个单元格的计算时间 $c_{i,j}$。第 $i+1$ 行的第 $j$ 个数表示位于第 $i-1$ 和第 $i$ 条平行线，第 $j-1$ 和第 $j$ 条子午线之间的单元格需要的计算时间。

输出格式

输出一行一个整数，表示最优的计算时间。

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

数据范围与提示

对于 $40\%$ 的数据，$n\le 10,m\le 10$；
对于全部数据，$1\le r<n\le 18,1\le s<m\le 18$，$1\le i\le n,1\le j\le m,0\le c_{i,j}\le 2\times 10^6$。