4378: 「BalticOI 2008」网格

**题目译自 [BalticOI 2008](http://b08.oi.edu.pl/downloads/booklet.pdf) Day2「[Grid](https://main.edu.pl/en/archive/boi/2008/gri)」** 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