高桥的章鱼小丸子店使用的章鱼小丸子，是一种根据地方的不同，味道也会不同的极具个性的章鱼小丸子。

另外，根据店员的能力不同，一次烤章鱼烧的数量也不同。

高桥想让每个店员都尽量把章鱼烤得好吃。

考丸子的容器有$N \times N$个正方形格子。

每个格子的烤的美味程度都各不相同，是$Dij$。

每位店员一次能烤丸子的上限为$P_k$

而且每次烤的章鱼小丸子一定是在章鱼小丸子容器的长方形部分，必须全部使用。

请求出每个店员一次能烧的章鱼烧的美味之和的最大值。

假设店员开始烤章鱼丸子的时候，容器完全空着，可以在任何地方使用。

输入

输入以下形式从标准输入给出

N
D11 D12 ... D1N
D21 D22 ... D2N
...
DN1 DN2 ... DNN
Q
P1
P2
...
PQ

• 第一行章鱼烧器的一个边的大小表示整数$n (1 \le n \le 50)$

• 烧焦章鱼小丸子的美味数$dij (1\le dij\le 100)$

• 店员人数$q(1 \le q \le n^2)$赋予持续$Q$行各自的店员烧焦章鱼小丸子的表达数量的整数$Pk (1 \le Pk \le n^2)$。

输出

请给每位店员输出一次所烤章鱼烧的美味之和的最大值，并在输出的末尾另起一行。