AT_arc223_a [ARC223A] Unusual-Constraint Knapsack

$ N $ 個の荷物 $ 1,2,\dots,N $ があります。 荷物 $ i $ は重さが $ w_i $ で、価値が $ v_i $ です。 $ i=2,3,\dots,N $ について、以下が成り立っています。 - $ \sum_{j=1}^{i-1}{w_j}

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_t $ は以下の形式で与えられる。 > $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ $ \vdots $ $ w_N $ $ v_N $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、荷物 $ 1,3 $ の $ 2 $ つを選ぶと重さの合計は $ 10 $ であり、価値の合計は $ 5 $ です。 また、条件を満たす範囲で価値の合計を $ 6 $ 以上にできません。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 60 $ - $ 1 \leq w_i \leq W \leq 10^{18} $ - $ \sum_{j=1}^{i-1}{w_j}