G - Range Knapsack Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

1 から N までの番号が付けられた N 個のアイテムがあります。 アイテム i の 重み は W_i、価値 は V_i です。

Q 個のクエリが与えられるので、順に処理してください。 j 番目のクエリは以下の通りです。

  • 整数 L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N) が与えられる。 アイテム L_j,L_j+1,\dots,R_j のうちいくつか（0 個でもよい）を、重みの総和が C_j を超えないように選ぶとき、選んだアイテムの価値の総和が最大でいくつになるか求めよ。

制約

  • 1\leq N \leq 2\times 10^4
  • 1\leq Q \leq 2\times 10^5
  • 1\leq W_i \leq 500
  • 1\leq V_i \leq 10^9
  • 1\leq L_j \leq R_j \leq N
  • 1\leq C_j \leq 500
  • 入力は全て整数

入力

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

N
W_1 V_1
W_2 V_2
\vdots
W_N V_N
Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q

出力

Q 行出力せよ。 i 行目 (1\leq i \leq Q) には、i 番目のクエリに対する答えを出力せよ。

入力例 1

4
3 4
5 8
1 2
2 3
3
1 4 7
2 4 10
1 2 2

出力例 1

11
13
0

1 番目のクエリについて、アイテム 1,2,3,4 のうちアイテム 2,4 を選ぶと、重みの総和は 5+2=7 となり C_1=7 を超えず、価値の総和として 8+3=11 を達成できます。これが最大です。

2 番目のクエリについて、アイテム 2,3,4 全てを選んでも、重みの総和は 5+1+2=8 となり C_2=10 を超えず、価値の総和として 8+2+3=13 を達成できます。

3 番目のクエリについて、アイテム 1,2 のいずれも重みが C_3=2 を超えているため、一つもアイテムを選ぶことができず、価値の総和の最大値は 0 になります。

入力例 2

8
167 430302156
22 623690081
197 476190629
176 24979445
22 877914575
247 211047202
232 822804784
25 628894325
8
6 8 176
3 5 80
1 7 310
4 8 368
4 5 218
3 4 431
4 6 228
1 1 239

出力例 2

628894325
877914575
2324409440
2329613684
902894020
501170074
902894020
430302156

Score : 575 points

Problem Statement

There are N items numbered from 1 to N. The weight of item i is W_i and the value is V_i.

You are given Q queries, so process them in order. The j-th query is as follows:

  • Integers L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N) are given. When choosing some (possibly zero) items from items L_j,L_j+1,\dots,R_j such that the total weight does not exceed C_j, find the maximum possible total value of the chosen items.

Constraints

  • 1\leq N \leq 2\times 10^4
  • 1\leq Q \leq 2\times 10^5
  • 1\leq W_i \leq 500
  • 1\leq V_i \leq 10^9
  • 1\leq L_j \leq R_j \leq N
  • 1\leq C_j \leq 500
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
W_1 V_1
W_2 V_2
\vdots
W_N V_N
Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q

Output

Output Q lines. The i-th line (1\leq i \leq Q) should contain the answer for the i-th query.

Sample Input 1

4
3 4
5 8
1 2
2 3
3
1 4 7
2 4 10
1 2 2

Sample Output 1

11
13
0

For the first query, among items 1,2,3,4, if you choose items 2,4, the total weight is 5+2=7, which does not exceed C_1=7, and the total value is 8+3=11. This is the maximum.

For the second query, even if you choose all items 2,3,4, the total weight is 5+1+2=8, which does not exceed C_2=10, and you can achieve a total value of 8+2+3=13.

For the third query, both items 1,2 have weights exceeding C_3=2, so you cannot choose any item, and the maximum total value is 0.

Sample Input 2

8
167 430302156
22 623690081
197 476190629
176 24979445
22 877914575
247 211047202
232 822804784
25 628894325
8
6 8 176
3 5 80
1 7 310
4 8 368
4 5 218
3 4 431
4 6 228
1 1 239

Sample Output 2

628894325
877914575
2324409440
2329613684
902894020
501170074
902894020
430302156