AT_abc426_g [ABC426G] Range Knapsack Query

$ 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 $ を超えないように選ぶとき、選んだアイテムの価値の総和が最大でいくつになるか求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 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 $ になります。 ### 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 $ - 入力は全て整数