/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
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 となり、これが最大です。
Score : 400 points
Problem Statement
We have N pieces of baggage called Baggage 1 through N, and M boxes called Box 1 through M.
Baggage i has a size of W_i and a value of V_i.
Box i can contain a piece of baggage whose size of at most X_i. It cannot contain two or more pieces of baggage.
You will be given Q queries. In each query, given two integers L and R, solve the following problem:
- Problem: Out of the M boxes, R-L+1 boxes, Box L,L+1,\ldots,R, have become unavailable. Find the maximum possible total value of a set of baggage that we can put into the remaining boxes simultaneously.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M Q
W_1 V_1
\vdots
W_N V_N
X_1 \ldots X_M
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q
Each Query is in the following format:
L R
Output
Print Q lines.
The i-th line should contain the answer to the problem described by \mathrm{Query}_i.
Sample Input 1
3 4 3 1 9 5 3 7 8 1 8 6 9 4 4 1 4 1 3
Sample Output 1
20 0 9
In the 1-st query, only Box 4 is unavailable. By putting Baggage 1 into Box 1, Baggage 3 into Box 2, and Baggage 2 into Box 3, we can put all baggage into boxes, making the total value of baggage in boxes 20.
In the 2-nd query, all boxes are unavailable; the answer is 0.
In the 3-rd query, only Box 4 is available. By putting Baggage 1 into Box 4, we can make the total value of baggage in boxes 9, which is the maximum possible result.