问题 1994. -- 子矩阵变形问题

1994: 子矩阵变形问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 72  解决: 20
[提交][状态][讨论版]

题目描述

魔法世界的军团接到神秘人的情报，获得了天顶星人所在的位置，司令部决定轰炸天顶星人所在的平原，已知平原为矩形，可划分为M行N列，（0<M≤N≤3000），天顶星人的基地分布在这些交叉点上，每个基地有R个人（0≤R≤100），暗物质炸弹威力呈方形，大小为W行H列，范围内的所有人将被消灭。请编程输出一个暗物质炸弹最多消灭多少人。

输入

第一行为两个数，表示Ｍ和Ｎ。第二行为两个数，表示Ｗ和Ｈ。以后各行表示基地分布。

输出

输出一个炸弹最多消灭多少人。

样例输入

2 2
1 1
2 0
1 0

样例输出

2

提示

对于80%数据，1≤M，N≤1000，对于100%数据，1≤M，N≤3000

来源

动态规划

[提交][状态]