问题 I: 郊游

问题 I: 郊游

时间限制: 1 Sec  内存限制: 128 MB
提交: 13  解决: 6
[状态] [提交] [命题人:]

题目描述

小朋友们出去郊游,明明和亮亮负责在草地上开一个篝火晚会。这个草地你可以认为是又 N * M 块单位长度为1的小正方形的草组成。

显然有的地方草长的好,有的地方长的不好,坐在上面显然舒服度是不一样的,于是每一块草都有一个舒服度 F

现在明明和亮亮要选定一个 a*b 的草场作为晚会的地点,小朋友们就坐在上面,显然他希望小朋友们坐的最舒服!

不过别急,篝火晚会怎么能少了篝火呢,篝火需要占用 c*d 的草地,当然,篝火必须严格放置在选定的草地的内部,也就是说,篝火的边界不能和选定操场的边界有公共部分,不然学生们怎么围着篝火开晚会呢?

给定 N*M 大草地每一块的舒服度,寻找一个 a*b 的草地,除去一个严格内部的 c*d 的子草地,使得总的舒服度最大。

输入

1行:6个整数,M ,  N,  b,   a,   d,   c

2~N+1行:每行 M 个整数,第 ij列的整数 Fi,j 表示,第 ij列的单位草地的舒服度。

输出

一个整数,表示最大的舒服值。

样例输入 Copy

8 5 5 3 2 1 
1 5 10 3 7 1 2 5 
6 12 4 4 3 3 1 5 
2 4 3 1 6 6 19 8 
1 1 1 3 4 2 4 5 
6 6 3 3 3 2 2 2

样例输出 Copy

70

提示

该图片就是对样例的解释,阴影区域就是最佳的选择方案。

篝火不可以出现在选定草地的边界,否则学生们无法严格围住篝火。



【数据范围】

1 ≤ Fi,j ≤ 100

3 ≤ a ≤ N

3 ≤ b ≤ M

1 ≤ c ≤ a-2

1 ≤ d ≤ b-2

对于 40% 的数据 N,M ≤ 10

对于 60% 的数据 N,M ≤ 150

对于 100% 的数据 N,M ≤ 1000