题目描述

营地地图由 $R$ 行 $C$ 列格子组成。每个格子的数值为 $0$ 或 $1$：$0$ 表示空地，$1$ 表示有障碍。

小林必须选择一个连续的 $h$ 行、$w$ 列矩形区域作为营地。矩形的边必须与网格线平行，不能旋转，且必须完全位于地图内。清除一个有障碍的格子需要一次操作。

请计算，为使选中的营地内没有障碍，最少需要多少次清除操作。

输入格式

第一行四个整数 $R,C,h,w$。

接下来 $R$ 行，每行 $C$ 个整数，表示地图。

输出格式

输出一个整数，表示最少清除操作次数。

3 4 2 2
1 0 1 0
0 0 1 0
1 1 0 0

1

1 3 1 2
0 0 1

0

样例 1 解释

选择左上角为第 $1$ 行第 $1$ 列的 $2\times2$ 矩形，只需要清除一个障碍；其他位置也无法做到清除零个障碍。

样例 2 解释

选择前两个格子，它们都是空地，答案为 $0$。

数据范围与提示

对于所有测试点：$1\le R,C\le1000$，$1\le h\le R$，$1\le w\le C$；地图中每个数都是 $0$ 或 $1$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$R,C\le6$
6—10	$R,C\le50$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。