D - おいしいたこ焼きの焼き方 Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

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

たこ焼き器は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点が与えられる。

入力例 1

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

出力例 1

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

入力例 2

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

出力例 2

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