AT_abc426_g [ABC426G] Range Knapsack Query

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.

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 $ Q $ lines. The $ i $ -th line $ (1\leq i \leq Q) $ should contain the answer for the $ i $ -th query.

### Sample Explanation 1 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 $ . ### 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.