题目描述

Aki 在做烤盘美味度分析。有一个 $n\times n$ 的烤盘网格，第 $i$ 行第 $j$ 列的格子美味度为 $a_{i,j}$（可能为负数）。

Aki 会不断提出查询：给定一个面积上限 $P$，他想知道——在所有面积不超过 $P$ 的子矩形中，美味度之和的最大值是多少。

请你对每个查询输出答案。

输入格式

• 第一行一个整数 $n$。
• 接下来 $n$ 行，每行 $n$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,n}$。
• 接下来一行一个整数 $q$，表示查询次数。
• 接下来 $q$ 行，每行一个整数 $P$。

数据规模：

• $1\le n\le 10$
• $1\le q\le 20$
• $-100\le a_{i,j}\le 100$
• $1\le P\le n^2$

输出格式

输出 $q$ 行，每行一个整数，表示对应查询的最大子矩形和。

3
1 2 3
-1 0 1
2 -2 4
3
1
4
9

4
8
10

Hint

样例解释：

• 当 $P=1$，只能选单个格子，最大是 4。
• 当 $P=4$，可以选面积不超过 4 的子矩形，综合比较可得最大为 8。
• 当 $P=9$，可以选整个矩阵，和为 10。