← 返回题目列表

AtCoder · abc005_4

D. 如何制作美味的章鱼烧

中文机器翻译题面 查看原题

問題文

高桥君的章鱼烧店使用的章鱼烧机是一种独特的章鱼烧机,其美味会根据您烘烤的地方而变化。
另外,根据工作人员的技术,一次可以煮的章鱼烧数量也有所不同。
高桥先生希望每位员工都能做出尽可能美味的章鱼烧。

章鱼烧制造商是 它具有N×N方形形状。
每个地点都有美味的章鱼烧D_{ij}已确定。
每个工作人员一次可以烹饪的章鱼烧数量都有限制。P_k已确定。
另外,一次烤章鱼烧时,章鱼烧机总是有一个长方形的部分,你必须使用里面的所有东西。
求每个工作人员一次可以烹制的章鱼烧总美味的最大值。
然而,当工作人员开始烧烤时,章鱼烧机已经完全空了,可以在任何地方使用。

入力

输入是按以下格式从标准输入给出的。
N
D_{11} D_{12} ... D_{1N}
D_{21} D_{22} ... D_{2N}
...
D_{N1} D_{N2} ... D_{NN}
Q
P_1
P_2
...
P_Q
  • 第一行是一个整数,表示章鱼烧设备一侧的尺寸。 给出了N(1≦N≦50)。
  • 继续N整数行代表章鱼烧机上每个位置烹制的章鱼烧的美味程度。D_{ij}(1≦D_{ij}≦100)。
  • 下一行是一个整数,表示职员的数量。 给出Q(1≦Q≦N^2)。
  • 继续Q一个整数,表示该行中每个工作人员可以制作的章鱼烧数量。P_k(1≦P_k≦N^2)。

出力

请输出每位工作人员一次可以烤出的章鱼烧总美味值的最大值。
另外,请在输出末尾插入换行符。 如果您正确回答了满足

部分点

1≦N≦5的所有测试用例,100满分 给出 50点。


入力例 1

3
3 2 1
2 2 1
1 1 1
3
1
4
9

出力例 1

3
9
14
  • 第一位店员说,如果在左上角烤章鱼烧,总的美味会增加。3。
  • 第二位工作人员在左上角的2x2区域烤章鱼烧,以增加总的美味。9。
  • 第三名工作人员可以使用所有的章鱼烧机器,所以总的美味是14。
这将是部分点中包含的输入。

入力例 2

3
1 1 1
1 1 1
9 9 9
1
4

出力例 2

27
  • 如果在最下面一排的1x3区域烤章鱼烧,总的美味会增加。27。
  • 这位店员可以烤4个章鱼烧,但如果只烤3个,总的美味会更大。
这将是部分点中包含的输入。