D - お買い物プラン 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君はショッピングモールで買い物をする計画を立てています。

モールには N 個の商品が一列に並んでおり、左から順に 1, 2, \ldots, N の番号がついています。

i 番目の商品の価格は H_i 円、満足度は V_i です。

また、正の整数 M が与えられます。各商品の価格および各回の予算はいずれも M 円以下です。

高橋君はこれから Q 回の買い物に出かけます。

j 回目の買い物では、L_j 番目から R_j 番目までの商品だけが購入の候補となり、予算は X_j 円です。

各回の買い物は互いに独立です。つまり、ある回で商品を購入しても、他の回の商品の在庫には影響しません。

各 j = 1, 2, \ldots, Q について、次の問いに答えてください。

L_j 番目から R_j 番目までの商品の中から 0 個以上を選びます。ただし、各商品は最大 1 個までしか選べません。選んだ商品の価格の合計が X_j 円以下となるように選ぶとき、選んだ商品の満足度の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 300
  • 1 \leq M \leq 500
  • 1 \leq Q \leq 100\,000
  • 1 \leq H_i \leq M (1 \leq i \leq N)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 1 \leq X_j \leq M (1 \leq j \leq Q)
  • 入力はすべて整数

入力

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

N M Q
H_1 V_1
H_2 V_2
\vdots
H_N V_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q
  • 1 行目には、商品の個数 N、価格・予算の上限 M、買い物の回数 Q が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目の商品の価格 H_i と満足度 V_i が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、j 回目の買い物で候補となる商品の範囲 L_j, R_j と予算 X_j が、スペース区切りで与えられる。

出力

Q 行出力せよ。

j 行目には、j 回目の買い物で得られる満足度の合計の最大値を出力せよ。

入力例 1

4 10 5
3 30
4 50
5 60
2 20
1 4 7
1 3 5
2 4 6
3 3 10
1 4 10

出力例 1

80
60
70
60
110

入力例 2

5 8 6
8 100
7 90
3 20
2 15
5 45
1 2 6
3 5 5
1 5 8
4 4 1
2 5 7
1 5 3

出力例 2

0
45
100
0
90
20

入力例 3

10 50 12
6 40
12 100
7 55
20 180
5 35
9 70
15 120
4 25
11 95
8 60
1 10 25
1 5 18
6 10 20
3 8 16
2 9 30
4 4 50
5 7 14
8 10 12
1 3 13
2 6 22
7 10 40
1 10 50

出力例 3

215
140
165
125
250
180
105
95
100
180
300
430

入力例 4

30 100 20
17 120
23 210
5 45
42 500
9 80
31 330
12 105
28 270
6 50
19 160
35 410
14 115
8 75
26 260
11 90
39 480
7 65
21 190
33 350
4 30
16 140
29 300
10 85
45 600
13 110
24 230
3 25
37 430
18 155
15 130
1 30 100
1 10 50
11 20 60
21 30 70
5 25 80
3 15 40
16 30 90
1 1 100
30 30 14
8 22 55
12 28 75
2 29 100
4 18 65
7 13 30
19 24 85
20 27 20
6 6 31
9 17 45
14 30 95
1 30 10

出力例 4

1225
550
670
830
1010
455
1110
120
0
620
900
1225
740
270
985
170
330
530
1175
90

入力例 5

1 1 1
1 1000000000
1 1 1

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is planning to go shopping at a shopping mall.

There are N items lined up in a row at the mall, numbered 1, 2, \ldots, N from left to right.

The price of the i-th item is H_i yen, and its satisfaction value is V_i.

A positive integer M is also given. The price of each item and the budget for each shopping trip are all at most M yen.

Takahashi will go shopping Q times.

On the j-th shopping trip, only items from the L_j-th to the R_j-th are available for purchase, and his budget is X_j yen.

Each shopping trip is independent of the others. That is, purchasing an item on one trip does not affect the stock of items on other trips.

For each j = 1, 2, \ldots, Q, answer the following question:

From the items numbered L_j through R_j, select 0 or more items. Each item can be selected at most once. Find the maximum total satisfaction value of the selected items such that the total price of the selected items does not exceed X_j yen.

Constraints

  • 1 \leq N \leq 300
  • 1 \leq M \leq 500
  • 1 \leq Q \leq 100\,000
  • 1 \leq H_i \leq M (1 \leq i \leq N)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 1 \leq X_j \leq M (1 \leq j \leq Q)
  • All inputs are integers

Input

The input is given from standard input in the following format:

N M Q
H_1 V_1
H_2 V_2
\vdots
H_N V_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q
  • The first line contains the number of items N, the upper limit on prices and budgets M, and the number of shopping trips Q, separated by spaces.
  • In the following N lines, the i-th line contains the price H_i and satisfaction value V_i of the i-th item, separated by a space.
  • In the following Q lines, the j-th line contains the range of candidate items L_j, R_j and the budget X_j for the j-th shopping trip, separated by spaces.

Output

Output Q lines.

On the j-th line, output the maximum total satisfaction value obtainable on the j-th shopping trip.

Sample Input 1

4 10 5
3 30
4 50
5 60
2 20
1 4 7
1 3 5
2 4 6
3 3 10
1 4 10

Sample Output 1

80
60
70
60
110

Sample Input 2

5 8 6
8 100
7 90
3 20
2 15
5 45
1 2 6
3 5 5
1 5 8
4 4 1
2 5 7
1 5 3

Sample Output 2

0
45
100
0
90
20

Sample Input 3

10 50 12
6 40
12 100
7 55
20 180
5 35
9 70
15 120
4 25
11 95
8 60
1 10 25
1 5 18
6 10 20
3 8 16
2 9 30
4 4 50
5 7 14
8 10 12
1 3 13
2 6 22
7 10 40
1 10 50

Sample Output 3

215
140
165
125
250
180
105
95
100
180
300
430

Sample Input 4

30 100 20
17 120
23 210
5 45
42 500
9 80
31 330
12 105
28 270
6 50
19 160
35 410
14 115
8 75
26 260
11 90
39 480
7 65
21 190
33 350
4 30
16 140
29 300
10 85
45 600
13 110
24 230
3 25
37 430
18 155
15 130
1 30 100
1 10 50
11 20 60
21 30 70
5 25 80
3 15 40
16 30 90
1 1 100
30 30 14
8 22 55
12 28 75
2 29 100
4 18 65
7 13 30
19 24 85
20 27 20
6 6 31
9 17 45
14 30 95
1 30 10

Sample Output 4

1225
550
670
830
1010
455
1110
120
0
620
900
1225
740
270
985
170
330
530
1175
90

Sample Input 5

1 1 1
1 1000000000
1 1 1

Sample Output 5

1000000000