1023:桃子问题

Time/Memory Limit:1000 MS/32768 K
Submitted: 428 Accepted: 153

 Problem Description

tong找到n个桃子,要将它们放入容量为v的背包带走。tong是个贪心的人,他要在自己的背包里面装最大的价钱的桃子,但是他不知道何时是最大值,因为能装入背包的值很多种,所以tong要ACMer帮忙,要求:给出n个桃子的体积和价钱,出能放入背包的桃子的总价钱最大值。

 Input

有多组测试数据,每组测试数据第一行为2个正整数,分别代表苹果的个数n和背包的容量v。n、v同时为0时结束测试,此时不输出。接下来的n行,每行2个正整数,用空格隔开,分别代表桃子的体积c和价钱w。所有输入数字的范围大于等于0,小于等于1000。

 Output

对每组测试数据输出一个整数,代表能放入背包的桃子的总价值。

 Sample Input

3 8
2 1
4 3
3 2
0 0

 Sample Output

5

 Author

yaonie

 Recommend

zh