← 返回题目列表

AtCoder · arc223_a

A. 异常约束背包

中文机器翻译题面 查看原题

分数: 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.
找出所选项目的最大可能总值。
解决 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 和 3 给出的总重量为 10 和总价值 5.
而且,不可能达到总价值 6 或更多,同时满足条件。