#AT5. Knapsack 2
Knapsack 2
[E] Knapsack 2(dp_e)
来源: AtCoder Educational DP Contest - Problem E 原题时限:2 秒 / 内存:1024 MB
题目描述
有 件物品,编号为 。
对于每个 (),第 件物品的重量为 ,价值为 。
太郎决定从中挑选若干件物品,装进背包带回家。背包的容量为 ,即所选物品的重量之和不能超过 。
求太郎带回家的物品价值之和的最大值。
输入格式
输入由标准输入按以下格式给出:
N W
w_1 v_1
w_2 v_2
:
w_N v_N
输出格式
输出太郎带回家的物品价值之和的最大值。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
3 8
3 30
4 50
5 60
输出:
90
样例 2
输入:
1 1000000000
1000000000 10
输出:
10
样例 3
输入:
6 15
6 5
5 6
6 4
6 6
3 5
7 2
输出:
17