1408: 离岸政策

题目描述

方块大陆由 $n\times m$ 块正方形区块作为最小单元构成，每个区块上都生活着或多或少的方块居民，有着不同的资源，因此也有着不同的地区实力。

Circle 国王在攻占了方块大陆后，意识到由自己直接管辖这片大陆不是一个很好的方案，这十分的消耗人力物力财力。于是他决定在这片大陆上扶植一个共同体，名字为“方块联盟”。为了让这片大陆上的人和睦相处~~也为了巩固自己的统治~~，Circle 国王决定将这片大陆以方块人喜欢的方式切割成多个国家。他先将这片大陆以横线划分成 $a$ 块，再用竖线分别将每块分割成 $b$ 块，形成 $a\times b$ 个国家。同时，为了防止出现一国独大而影响了公平~~统治与搅屎~~，他还希望能让国力（所包含的所有区块的地区实力之和）最弱小的国家的国力尽可能的强。因此，他想知道国力最弱的国家的国力可能的最大值是多少。

分割样例：

```text 1 2 | 2 1

3 | 1 1 1

2 0 1 | 3

1 1 | 1 1 1 1 | 1 1 ```

输入格式

第一行的输入 $n,m,a,b$

对于接下来的 $n$ 行的输入，每行输入 $m$ 个数，代表一个区块的地区实力 $p$ 。

输出格式

仅一行，输出国力最弱的国家的国力可能的最大值 $ans$

样例输入

text 5 4 4 2 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1

样例输出

text 3

数据范围

对于 10% 的数据，$n,m\leq10$

对于 30% 的数据，$n,m\leq100$ ，$0\leq p\leq1$ ，$\Sigma\Sigma p_{ij}\leq 20$

对于 20% 的数据，$n,m\leq300$ ，$0\leq p\leq1$ ，$\Sigma\Sigma p_{ij}\leq 10000$

对于所有的数据有 $n,m\leq500$ ，$p\leq8000$， $1\leq a\leq n$， $1\leq b\leq m$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！