← 返回题目列表

AtCoder · dp_e

E. 背包 2

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

分数: 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^9
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^3

输入

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

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

1 1000000000
1000000000 10

示例输出 2

10

示例输入 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.