-
完全背包
题目ID：11059必做题100分
最新提交：
Runtime Error
50 分
历史最高：
Wrong Answer
75 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
【问题描述】小 Q 现在遇到了一道完全背包模板题，可是他不会做，请你帮帮他。
现有
n
n 件物品，每种物品有无限个，每种物品有一定的重量
w
i
wi 和价值
v
i
vi。问你在选择的物品的重量之和小于或等于
W
W 的情况下最大的价值和为多少。
【输入格式】
第一行两个整数，
n
n 和
W
W。
接下来
n
n 行，每行两个正整数，第
i
i 个物品的重量
w
i
wi 和价值
v
i
vi。
【输出格式】
一行一个非负整数，表示最大的价值和。
【输入样例1】
1 10
3 2
【输出样例1】
6
【输入样例2】
5 10
1 1
2 2
3 3
4 4
5 5
【输出样例2】
10
【输入样例3】
5 10
1 1
2 3
3 3
4 8
5 7
【输出样例3】
19
【数据范围与约定】
对于 20％ 的数据，
1
≤
n
≤
1000
，
1
≤
W
≤
1000
1≤n≤1000，1≤W≤1000
对于 30％ 的数据，
1
≤
W
≤
10000
1≤W≤10000
对于 45％ 的数据，
1
≤
n
≤
10000
1≤n≤10000
对于 100％ 的数据，
1
≤
n
≤
1000000
，
1
≤
W
≤
1
0
10
，
1
≤
w
i
≤
100
，
1
≤
v
i
≤
1
0
8
1≤n≤1000000，1≤W≤10
10
，1≤w
i
≤100，1≤v
i
≤10
8