You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

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

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

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

考丸子的容器有$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)$。

输出

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

题目描述

高橋君のたこ焼き屋で使っているたこ焼き器は焼く場所によって美味しさの変わるクセの強いたこ焼き器です。 また、店員の力量によって一度に焼けるたこ焼きの数が違います。 高橋君はそれぞれの店員ができるだけ美味しくたこ焼きを焼けるようにしようと思いました。

たこ焼き器は$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$行にたこ焼き器のそれぞれの場所で焼けるたこ焼きの美味しさを表す整数$D_{ij}(1≦D_{ij}≦100)$が与えられます。
• 次の行に店員の人数を表す整数$Q$($1≦Q≦N^2$)が与えられます。
• 続く$Q$行にそれぞれの店員が焼けるたこ焼きの数を表す整数$P_k(1≦P_k≦N^2)$が与えられます。

それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を出力して下さい。 また、出力の末尾には改行を入れて下さい。$1≦N≦5$を満たすテストケース全てに正解すると、$100$点満点のうち $50$点が与えられる。

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

3
9
14

• １人目の店員は左上でたこ焼きを焼くと美味しさの合計が$3$になります。
• ２人目の店員は左上の2×2の範囲でたこ焼きを焼くと美味しさの合計が$9$になります。
• ３人目の店員はたこ焼き器全てを使えるので美味しさの合計が$14$になります。

これは部分点に含まれる入力になります。 ```

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

27

- 一番下の列の範囲1×3でたこ焼きを焼くと美味しさの合計が$ 27 $になります。
- この店員はたこ焼きを４個焼くことができますが、３個しか焼かないほうが美味しさの合計が大きくなります。
 
 これは部分点に含まれる入力になります。

## 输入格式

## 输出格式