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 翻译