题目描述
有 N 件物品,第 i 件物品的重量和价值分别为 wi 与 vi。它们满足超递增条件:对每个 i≥2,都有 ∑j=1i−1wj<wi。请选出总重量不超过 W 的物品,使总价值最大。
输入格式
从 weight.in 文件读入数据。
第一行是测试组数 T。每组数据先给出 N,W,随后 N 行每行输入 wi,vi。
输出格式
将结果输出到 weight.out 文件。
输出 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≤T≤2×105,1≤N≤60,1≤wi≤W≤1018,1≤vi≤1016,且 ∑j=1i−1wj<wi(2≤i≤N)。所有测试组中 N 的总和不超过 2×105。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 |
分值 |
测试点 |
附加条件 |
| 1 |
10 |
1∼4 |
N≤20 |
| 2 |
20 |
5∼8 |
N≤30 |
| 3 |
30 |
9∼14 |
N≤60 |
| 4 |
40 |
15∼20 |
满足全部限制,且所有测试组总规模受限 |