1024:无限桃子问题

Time/Memory Limit:1000 MS/32768 K
Submitted: 229 Accepted: 107

 Problem Description

tong找到n种桃子,而且每种都有无限多个,要将它们放入容量为v的背包。显然,tong还是一个贪心的人,他要在有限的背包中装入最大的桃子价钱,给出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

6

 Author

yaonie

 Recommend

zh