← 返回题目列表

AtCoder · arc051_d

D. 矩形

中文机器翻译题面 查看原题

問題文

长度 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