問題文
另外,根据工作人员的技术,一次可以煮的章鱼烧数量也有所不同。
高桥先生希望每位员工都能做出尽可能美味的章鱼烧。
章鱼烧制造商是 它具有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个,总的美味会更大。