505 - 01背包

通过次数

100

提交次数

160

时间限制 : 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

输出

14