#P4956. 射命丸文

射命丸文

题目描述

在幻想乡,射命丸文是以偷拍闻名的鸦天狗。她的照相机不仅能照相,还能消除取景框内所有的弹幕,并获得该区域内所有弹幕的分值总和。

现有一块 NNMM 列的弹幕群,每个单位面积的弹幕分值为 num[i][j]num[i][j]。相机的取景框可消除一块 RRCC 列的弹幕,文文希望获得尽可能多的分值,请求出她最多能得到的分值。

输入格式

第一行包含四个正整数 N,M,R,CN, M, R, C,分别表示弹幕群的行数、列数,以及取景框的行数和列数。
接下来的 NN 行,每行包含 MM 个正整数,第 i+1i+1 行第 jj 个数表示 num[i][j]num[i][j](行列下标均从 00 开始)。

输出格式

一行一个整数,表示能取得的最大得分。

样例

3 5 2 3
5 2 7 1 1
5 9 5 1 5
3 5 1 5 3
33

样例解释
取景框大小为 2233 列,最优区域为第 00 行至第 11 行、第 00 列至第 22 列:

  • 00 行:5,2,75, 2, 7
  • 11 行:5,9,55, 9, 5
    总和为 5+2+7+5+9+5=335 + 2 + 7 + 5 + 9 + 5 = 33,这是所有可能区域中的最大值。

数据范围

  • 1N,M2001 \leq N, M \leq 2001RN1 \leq R \leq N1CM1 \leq C \leq M
  • 1num[i][j]10001 \leq num[i][j] \leq 1000
  • 保证结果在 int 范围内。