Problem1131--图灵的又一个背包

1131: 图灵的又一个背包

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 50  Solved: 26
[Status] [Submit] [Creator:]

Description

图灵外出旅行,他背了一个容量为 C 的背包,现在他面前有 n 种物品,每种物品数量无限,每一种物品 i 的重量是 wi,其价值为 vi。 

问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 

Input

第一行分别是n和C, 
第二行是到n+1行,每行两个数据,分别是wi和vi。

Output

输出一行一个数,为背包的最大价值!

Sample Input Copy

6 20
1 23
5 9
7 89
21 598
17 9
5 71

Sample Output Copy

460

HINT

n<=1000 ,C<=5000

Source/Category