题目描述

仓库里有 $n$ 件物品，第 $i$ 件物品的重量为 $w_i$，价值为 $v_i$。现在有一个容量为 $W$ 的箱子，你可以选择其中若干件物品装入箱子，每件物品至多选择一次，且装入物品的总重量不能超过 $W$。

请你求出：能够得到的最大总价值是多少。

输入格式

第一行输入两个整数 $n,W$。
接下来 $n$ 行，每行输入两个整数 $w_i,v_i$。
数据范围：

• $1 \le n \le 100$
• $1 \le W \le 5000$
• $1 \le w_i \le W$
• $0 \le v_i \le 10^6$

输出格式

输出一行，一个整数，表示最大总价值。

4 6
2 1
3 5
3 6
6 1

11

Hint

样例解释： 最优方案是选择第 $2$ 件和第 $3$ 件物品，总重量为 $3+3=6$，总价值为 $5+6=11$。