Problem1535--完全背包

1535: 完全背包

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 300  Solved: 142
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个容量为m的背包，有n种体积为vi，价值为wi的物品，每种物品的数量无限。
请问在不超过背包容量的情况下，PIPI能装下的物品的总价值最高是多少？

Input

多组输入。
第一行输入物品的种数n以及背包的容量m（1<=n,m<=1000）。
接下来有n行，每行输入第i种物品的体积vi和价值wi（0<=vi,wi<=1000）。

Output

输出能装下的物品的最高总价值。

Sample Input 

4 8
5 4
3 3
2 2
4 3

Sample Output 

8

Source/Category

简单 
[Submit] [Status]