506 - 完全背包

通过次数

86

提交次数

115

时间限制 : 1 秒
内存限制 : 128 MB

N 种物品和一个容量为 V 的背包。第i种物品的体积是 C_i ,得到的价值是 W_i。求解将哪些物品装入背包可使价值总和最大,每种物品有无数件。

输入

第一行是两个整数NV(1<=N,V<=1000)。 

接下来N行,每行有两个数C_iW_i(1<=C_i,W_i<=1000),分别代表体积和价值。

输出

输出能得到的最大价值。

样例

输入

5 10
1 5
2 4
3 3
4 2
5 1

输出

50