AT_arc051_d [ARC051D] 長方形

[problemUrl]: https://atcoder.jp/contests/arc051/tasks/arc051_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 $ つも選ばないことはできません。

入力は以下の形式で標準入力から与えられる。 > $ 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\ ≦\ W,\ H\ ≦\ 2000 $ - $ 1\ ≦\ Q\ ≦\ 2000 $ - $ 1\ ≦\ A\ ≦\ W $ - $ 1\ ≦\ B\ ≦\ H $ - $ -100,000\ ≦\ a_i,\ b_i\ ≦\ 100,000 $