题目描述

有一个 $N\times N$ 的方形烤盘，每个位置都有一个正整数收益 $D_{i,j}$。

每次只能选择一个矩形区域来使用，矩形内所有格子都会被使用。对于第 $k$ 个询问，给定一个上限 $P_k$，表示本次最多能使用 $P_k$ 个格子。请计算在不超过这个格子数量的前提下，能得到的最大收益总和。

输入格式

第一行输入整数 $N$。

接下来 $N$ 行，每行 $N$ 个整数，表示 $D_{i,j}$。

接下来一行输入整数 $Q$。

接下来 $Q$ 行，每行输入一个整数 $P_k$。

输出格式

对每个询问输出一行一个整数，表示答案。

样例

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

3
9
14

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

27

样例说明

数据范围

• 对于 $30\%$ 的数据，$N\le 5$。
• 对于 $60\%$ 的数据，$N\le 15$。
• 对于 $100\%$ 的数据，$1\le N\le 50$，$1\le D_{i,j}\le 100$，$1\le Q\le N^2$，$1\le P_k\le N^2$。