题目描述

$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$ 個の箱が使えなくなってしまいました。 残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。

输入格式

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

$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$ 到 $N$ 的 $N$ 个行李和编号为 $1$ 到 $M$ 的 $M$ 个箱子。

行李 $i$ 的大小是 $W_i$，价值是 $Vi$。

箱子 $i$ 可以放入大小 $X_i$ 以下的行李。$1$ 个箱子不能放 $2$ 件及以上的行李。

给出 $Q$ 个查询。每个查询都会给出 $2$ 个整数 $L,R$，请解决下面的问题。

问题: 在这 $M$ 个箱子中，区间 $[L,R]$ 的 $R - L+ 1$ 个箱子不能使用了。请求剩下的箱子里能放入的行李的总价值的最大值。

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

20
0
9

提示

制約

• $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$
• 入力は全て整数

Sample Explanation 1

$1$ 番目のクエリでは箱 $4$ が使えません。 箱 $1$ に荷物 $1$ を、箱 $2$ に荷物 $3$ を、箱 $3$ に荷物 $2$ を入れることで、 全ての荷物を箱の中に入れることができ、箱の中の荷物の価値の合計を $20$ にすることができます。 $2$ 番目のクエリでは全ての箱が使えません。したがって、答えは $0$ です。 $3$ 番目のクエリでは、箱 $4$ だけが使えます。箱 $4$ に荷物 $1$ を入れることで、箱の中の荷物の価値の合計は $9$ となり、これが最大です。