#AT4. Knapsack 1
Knapsack 1
[D] Knapsack 1(dp_d)
来源: AtCoder Educational DP Contest - Problem D 原题时限: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
输入:
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
输出:
5000000000
样例 3
输入:
6 15
6 5
5 6
6 4
6 6
3 5
7 2
输出:
17