题目描述

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$，价值是 $D_i$。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

第一行：物品个数 $N$ 和背包大小 $M$。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$。

输出格式

输出一行最大价值。

样例

4 6
1 4
2 6
3 12
2 7

23

数据范围

• $1 \le N \le 3402$
• $1 \le M \le 12880$
• $1 \le W_i \le 400$
• $1 \le D_i \le 100$