AT_abc005_4.[ABC005D] おいしいたこ焼きの焼き方

高桥君的章鱼烧店里使用的章鱼烧烤盘有一个很大的特点：不同位置烤出来的章鱼烧美味程度不同。
另外，根据店员的能力，每次能烤的章鱼烧数量也不同。
高桥君希望让每位店员都能尽可能烤出最美味的章鱼烧。

章鱼烧烤盘是一个 $N \times 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$

• 第 1 行输入一个整数 $N$，表示章鱼烧烤盘的边长，$1 \leq N \leq 50$。
• 接下来的 $N$ 行，每行输入 $N$ 个整数 $D_{ij}$，表示每个位置的章鱼烧美味度，$1 \leq D_{ij} \leq 100$。
• 接下来一行输入一个整数 $Q$，表示店员人数，$1 \leq Q \leq N^2$。
• 接下来的 $Q$ 行，每行输入一个整数 $P_k$，表示第 $k$ 位店员一次最多能烤的章鱼烧数量，$1 \leq P_k \leq N^2$。

对于每位店员，输出他一次能烤出的章鱼烧美味度总和的最大值。
每个答案输出后请换行。

如果你能正确解决所有 $1 \leq N \leq 5$ 的测试点，可以获得满分 $100$ 分中的 $50$ 分。

示例：

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

3
9
14

• 第 1 位店员在左上角烤章鱼烧时美味度总和为 $3$。
• 第 2 位店员在左上角 $2 \times 2$ 的区域烤章鱼烧时美味度总和为 $9$。
• 第 3 位店员可以用整个烤盘，最大美味度总和为 $14$。

这属于部分分的输入。

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

27

• 在最下方一行 $1 \times 3$ 的区域烤章鱼烧时美味度总和为 $27$。
• 这位店员最多能烤 $4$ 个章鱼烧，但只烤 $3$ 个反而美味度更高。

这属于部分分的输入。

第 1 行：一个整数 $N$，表示烤盘的边长。
接下来 $N$ 行：每行 $N$ 个整数 $D_{ij}$，表示每个位置的美味度。
接下来一行：一个整数 $Q$，表示店员人数。
接下来 $Q$ 行：每行一个整数 $P_k$，表示每位店员一次最多能烤的章鱼烧数量。

对于每位店员，输出他一次能烤出的章鱼烧美味度总和的最大值，每个答案一行。

• 对于 $1 \leq N \leq 5$ 的所有测试点，答对即可获得 $50$ 分。
• 你可以选择比 $P_k$ 更小的矩形区域，只要美味度总和更高即可。
• 每次烤的章鱼烧必须是烤盘上的一个矩形区域，且区域内所有位置都要用上。
• 每位店员开始烤的时候，烤盘是完全空的，可以选择任意位置。

由 ChatGPT 4.1 翻译