题目描述

有一个背包，最多可以装下总重量不超过 $W$ 的物品。

现在有 $n$ 个物品，每个物品只能选择一次。第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$。

请你选择若干个物品，使得它们的总重量不超过 $W$，并且总价值最大。

请输出能够获得的最大总价值。

输入格式

第一行包含两个整数 $n,W$，表示物品数量和背包容量。

接下来 $n$ 行，每行包含两个整数 $w_i,v_i$，表示第 $i$ 个物品的重量和价值。

输出格式

输出一个整数，表示在总重量不超过 $W$ 的情况下，能够获得的最大总价值。

输入输出样例 #1

输入 #1

4 10
6 30
3 14
4 16
2 9

输出 #1

46

说明/提示

样例中，选择第 $1$ 个和第 $3$ 个物品。

它们的总重量为：

它们的总价值为：

所以答案为 $46$。

数据范围

对于 $100\%$ 的数据：