Problem1130--图灵的背包

1130: 图灵的背包

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 118  Solved: 36
[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

192

HINT

n<=1000 ,C<=5000

Source/Category