问题描述

高桥君在他的章鱼烧店里使用的章鱼烧炉是一种会因为烹饪位置而改变味道的特殊烧烤炉。
此外，每个员工一次可以烹饪的章鱼烧数量也不同。
高桥君希望让每个员工都能尽可能地烹饪出美味的章鱼烧。

章鱼烧炉是一个 $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$ 行，每行包含 $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。
• 第二个员工在左上角的2×2区域烹饪章鱼烧，则美味程度之和为9。
• 第三个员工可以使用整个烧烤炉，所以美味程度之和为14。

这是一个包含部分分数的输入示例。

输入例子 2

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

输出例子 2

27

• 在最后一列的范围为1×3的区域烹饪章鱼烧，则美味程度之和为27。
• 这个员工可以烹饪4个章鱼烧，但只烹饪3个会使美味程度之和更大。

这是一个包含部分分数的输入示例。