F : 魔童降世 - 魔焰现

Progress Bar

时间限制:2 Sec 内存限制:64 MiB

提交


题目描述

生来便具有魔眼赤瞳,受上天咒罚,为世人所冷眼相待。失落,寂寞,无助,在内心冲击,但却从未动摇过内心深处那坚定的信念:

我命由我不由天

他要靠自己,去逆天改命,改变世人的观念,改变自己的命运,“任尔天劫千百重,我自傲骨撞苍穹”!

魔童降世系列 第一章 猖獗的海盗军团

他独自一人来到海边,享受着海风吹拂,难得有地方能够安然独处,不为旁人所指点,他慵懒地伸了伸懒腰,正打算小憩一会,但直觉告诉他,海中央似乎并不平静~~

果然,来到海面上空,星罗棋布的黑色战舰即刻映入眼帘,这是海盗们将要烧杀抢掠的前兆,这些战舰分布于 n × m 的矩形之中,过于常人的精神力可以探测得知每艘战舰中所携带的财富。

于是,他决定召唤魔焰进行攻击,当攻击点坐标为 (x, y) 时,位于 x 行的所有战舰,位于 y 列的所有战舰,以及以 (x, y) 为中心的边长为 k 的矩形中的战舰均会被摧毁,同时他能够 100% 收集被摧毁的战舰中所拥有的财富,并于日后赠予有困难的人。

因为他只能召唤一次魔焰,所以他想让能够搜集到的财富最大化,请你帮他预测,对于不同的魔焰涉及边长 k ,一次攻击之后所能得到的最大财富是多少。

输入描述

第一行输入两个整数 n, m,代表有可能存在黑色战舰的矩形范围,从上至下为 1 到 n 行, 从左至右为 1 到 m 列。  1 ≤ n, m ≤ 1000

接下来 n 行,每行 m 个数字,代表当前坐标的财富值 x,若 x = 0, 则表明当前坐标不存在战舰,或战舰内不存在任何财富。   0 ≤ x ≤ 1000

随后一行输入一个正整数 T,代表询问次数(T ≤ 10),对于每次询问,输入一行一个整数 k ,代表以 (x, y) 为攻击中心时,边长为 k 的矩形中的战舰也会被波及。   1 ≤ k ≤ 1000 且 k 一定为奇数

输出描述

对于每组询问,输出仅发动一次魔焰攻击后,所能获得的最大财富(每组询问的答案独占一行)。

样例输入

5 5
1 0 1 0 1
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0
1 0 1 0 1
2
3
11

样例输出

13
17

来源

逆乾