题目描述
给定 $n$ 个物品,每个物品的价值为 $v_i$,重量为 $w_i$,请从这些物品中选出一些,在它们的重量之和不超过一个给定值 $c$ 的前提下,价值之和达到最大。
注意本题中物品的重量可能比较大。
输入
第一行:两个整数 $n$ 与 $c$。
第二行到第 $n+1$ 行,第 $i+1$ 行有两个整数表示 $v_i$ 与 $w_i$
输出
单个整数:表示满足限定条件下的最大价值和。
样例输入输出
输入#1
复制
3 1000
90 900
53 550
38 400
提示
+ 对于 $30\%$ 的数据, $n\leq 20$;
+ 对于 $60\%$ 的数据, $c\leq 10000$;
+ 对于 $100\%$ 的数据, $1\leq n\leq 500$,$1\leq c\leq 10^{18}$,$1\leq v_i\leq 500$,$1\leq w_i\leq 10^{18}$。
样例1说明:选后两个物品