← 返回题目列表

AtCoder · dp_d

D. 背包 1

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

分数: 100 点

问题陈述

有 N 项目,已编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N),项目 i 的权重为 w_i 和值为 v_i.

太郎决定选择一些 N 物品并用背包将它们带回家。 背包的容量为 W,这意味着所取物品的重量之和最多不得超过 W.

找出太郎带回家的物品价值的最大可能总和。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 100
  • 1 \leq W \leq 10^5
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

输出

打印太郎带回家的物品的最大可能价值总和。


样本输入 1

3 8
3 30
4 50
5 60

示例输出 1

90

项目 应采取 1 和 3 。 那么权重之和就是 3 + 5 = 8,值的总和为 30 + 60 = 90.


示例输入 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

示例输出 2

5000000000

答案可能不适合 32 位整数类型。


示例输入 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

示例输出 3

17

项目 应采取 2, 4 和 5 。 那么权重之和就是 5 + 6 + 3 = 14,值的总和为 6 + 6 + 5 = 17.