题目描述

给定 $n$ 个物品，每个物品的价值为 $v_i$，重量为 $w_i$，请从这些物品中选出一些，在它们的重量之和不超过一个给定值 $c$ 的前提下，价值之和达到最大。

注意本题中物品的重量可能比较大。

输入格式

第一行：两个整数 $n$ 与 $c$。 第二行到第 $n+1$ 行，第 $i+1$ 行有两个整数表示 $v_i$ 与 $w_i$

输出格式

单个整数：表示满足限定条件下的最大价值和。

3 1000
90 900
53 550
38 400

91

样例解释 1

选后两个物品

数据范围

• 对于 $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}$。