/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 個の荷物 1,2,\dots,N があります。
荷物 i は重さが w_i で、価値が v_i です。
i=2,3,\dots,N について、以下が成り立っています。
- \sum_{j=1}^{i-1}{w_j}<w_i
重さの合計が W 以下になるようにいくつか（0 個でもよい）の荷物を選びます。
選んだ荷物の価値の合計としてあり得る値の最大値を求めてください。
1 つの入力につき、T 個のテストケースを解いてください。
制約
- 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}<w_i \; (2 \leq i \leq N)
- 1 \leq v_i \leq 10^{16}
- すべてのテストケースにおける N の総和は 2 \times 10^5 以下
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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 番目のテストケースの答えを出力せよ。
入力例 1
3 3 10 1 2 3 1 9 3 3 20 1 2 3 1 9 3 4 15 1 1 3 2 5 3 10 4
出力例 1
5 6 7
1 つ目のテストケースでは、荷物 1,3 の 2 つを選ぶと重さの合計は 10 であり、価値の合計は 5 です。
また、条件を満たす範囲で価値の合計を 6 以上にできません。
Score : 400 points
Problem Statement
There are N items 1, 2, \dots, N.
Item i has weight w_i and value v_i.
For i = 2, 3, \dots, N, the following holds:
- \sum_{j=1}^{i-1}{w_j} < w_i
Choose some (possibly zero) items such that the total weight is at most W.
Find the maximum possible total value of the chosen items.
Solve T test cases per input.
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} < w_i \; (2 \leq i \leq N)
- 1 \leq v_i \leq 10^{16}
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case \mathrm{case}_t is given in the following format:
N W w_1 v_1 w_2 v_2 \vdots w_N v_N
Output
Output the answers over a total of T lines. The t-th line should contain the answer for the t-th test case.
Sample Input 1
3 3 10 1 2 3 1 9 3 3 20 1 2 3 1 9 3 4 15 1 1 3 2 5 3 10 4
Sample Output 1
5 6 7
For the first test case, choosing items 1 and 3 gives a total weight of 10 and a total value of 5.
Moreover, it is impossible to achieve a total value of 6 or more while satisfying the condition.