問題文

$1$ から $N$ の番号がついた $N$ 個の荷物と、$1$ から $M$ の番号がついた $M$ 個の箱があります。

荷物 $i$ の大きさは $W_i$ で、価値は $V_i$ です。

箱 $i$ には大きさが $X_i$ 以下の荷物を入れることができます。$1$ つの箱に $2$ つ以上の荷物を入れることはできません。

$Q$ 個のクエリが与えられます。各クエリでは $2$ つの整数 $L,R$ が与えられるので、次の問題を解いてください。

• 問題：$M$ 個の箱のうち、箱 $L,L+1,\\ldots,R$ の $R-L+1$ 個の箱が使えなくなってしまいました。 残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。

制約

• $1 \\leq N \\leq 50$
• $1 \\leq M \\leq 50$
• $1 \\leq Q \\leq 50$
• $1 \\leq W_i \\leq 10^6$
• $1 \\leq V_i \\leq 10^6$
• $1 \\leq X_i \\leq 10^6$
• $1 \\leq L \\leq R \\leq M$
• 入力は全て整数

入力

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

$N$ $M$ $Q$ $W_1$ $V_1$ $\\vdots$ $W_N$ $V_N$ $X_1$ $\\ldots$ $X_M$ $\\mathrm{Query}_1$ $\\vdots$ $\\mathrm{Query}_Q$

各クエリは以下の形式で与えられる。

$L$ $R$

出力

$Q$ 行出力せよ。

$i$ 行目には、$\\mathrm{Query}_i$ に対応する問題の答えを出力せよ。

入力例 1

3 4 3
1 9
5 3
7 8
1 8 6 9
4 4
1 4
1 3

出力例 1

20
0
9

$1$ 番目のクエリでは箱 $4$ が使えません。 箱 $1$ に荷物 $1$ を、箱 $2$ に荷物 $3$ を、箱 $3$ に荷物 $2$ を入れることで、 全ての荷物を箱の中に入れることができ、箱の中の荷物の価値の合計を $20$ にすることができます。

$2$ 番目のクエリでは全ての箱が使えません。したがって、答えは $0$ です。

$3$ 番目のクエリでは、箱 $4$ だけが使えます。箱 $4$ に荷物 $1$ を入れることで、箱の中の荷物の価値の合計は $9$ となり、これが最大です。