D - 長方形 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

長さ W の数列 a_1, a_2, ..., a_W と、長さ H の数列 b_1, b_2, ..., b_H が与えられます。

左から i 番目、上から j 番目のマス目には a_i + b_j が書き込まれた、W \times H のマス目を考えます。

Q 個の以下のようなクエリが与えられるので、処理してください。

  • A, B が与えられるので、左から A 番目以内、上から B 番目以内のマス目たちの中から、選んだ部分が長方形になるように幾つかマス目を選んだ時の、選んだマス目の値の総和の最大値を出力。

なお、マス目を 1 つも選ばないことはできません。

制約

  • 1 ≦ W, H ≦ 2000
  • 1 ≦ Q ≦ 2000
  • 1 ≦ A ≦ W
  • 1 ≦ B ≦ H
  • -100,000 ≦ a_i, b_i ≦ 100,000

入力

入力は以下の形式で標準入力から与えられる。

W H
a_1 a_2 ... a_W
b_1 b_2 ... b_H
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q

ただし、A_i, B_i はそれぞれ i 個目のクエリの A, B を表します。

出力

Q 行出力する。

i 行目には、i 番目のクエリの結果を出力する。

入力例1

2 2
0 10
0 -1
4
1 1
1 2
2 1
2 2

出力例1

0
0
10
19

入力例2

3 3
1 10 100
1000 10000 100000
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

出力例2

1001
11002
111003
2011
22022
222033
3111
33222
333333

入力例3

10 8
2 -4 0 0 -1 4 5 0 -3 0
2 0 0 -3 -5 -5 -4 -4
10
2 6
1 4
1 2
5 7
1 5
7 6
7 4
1 5
3 5
10 7

出力例3

8
8
6
8
8
34
34
8
8
36