AT_arc051_d [ARC051D] 長方形

给定一个长度为 $W$ 的数列 $a_1, a_2, \ldots, a_W$ 和一个长度为 $H$ 的数列 $b_1, b_2, \ldots, b_H$。 现在，我们构造一个 $W \times H$ 的矩阵。矩阵中第 $i$ 列第 $j$ 行的格子的值为 $a_i + b_j$。 接下来有 $Q$ 个查询，每个查询要求如下： - 给定两个参数 $A$ 和 $B$，请在左上角 $A$ 列以内和 $B$ 行以内的所有格子中选择一些格子，要求这些格子组成一个矩形，并求出这些格子的值之和的最大值。注意，至少需要选择一个格子。

输入从标准输入读取，格式如下： > $W\ H\ a_1\ a_2\ \ldots\ a_W\ b_1\ b_2\ \ldots\ b_H\ Q\ A_1\ B_1\ A_2\ B_2\ \ldots\ A_Q\ B_Q$ 其中，$A_i$ 和 $B_i$ 分别是第 $i$ 个查询的参数 $A$ 和 $B$。

输出 $Q$ 行，每行一个整数，对应每个查询的最大值结果。结果按照查询给出的顺序输出。 ## 数据范围 - $1 \leq W, H \leq 2000$ - $1 \leq Q \leq 2000$ - $1 \leq A \leq W$ - $1 \leq B \leq H$ - $-100,000 \leq a_i, b_i \leq 100,000$ **本翻译由 AI 自动生成**

### 制約 - $ 1\ ≦\ W,\ H\ ≦\ 2000 $ - $ 1\ ≦\ Q\ ≦\ 2000 $ - $ 1\ ≦\ A\ ≦\ W $ - $ 1\ ≦\ B\ ≦\ H $ - $ -100,000\ ≦\ a_i,\ b_i\ ≦\ 100,000 $