AT_abc426_g.[ABC426G] Range Knapsack Query

有 $N$ 个物品，编号从 $1$ 到 $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$ 中选择若干（可以为零）个物品，使得总重量不超过 $C_j$，求所能获得的最大总价值。

输入按如下格式从标准输入读入：

$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

对于第一个查询，在物品 $1,2,3,4$ 中，若选择物品 $2,4$，总重量为 $5+2=7$，不超过 $C_1=7$，总价值为 $8+3=11$，已达最大值。

对于第二个查询，若选择所有物品 $2,3,4$，总重量为 $5+1+2=8$，不超过 $C_2=10$，总价值为 $8+2+3=13$。

对于第三个查询，物品 $1,2$ 的重量都超过了 $C_3=2$，所以无法选择任何物品，最大总价值为 $0$。

数据范围

• $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$
• 所有输入均为整数。

由 ChatGPT 5 翻译