C. 01背包 II

题目描述

有 $n$ 个物品，第 $i$ 个物品的重量是 $w_i$，价值是 $v_i$。 有一个承重上限为 $m$ 的背包，问背包能装的物品的价值和的最大值。

数据范围：

• $1 \le m \le 10^9$
• $1 \le n \le 100$
• $1 \le w_i \le m$
• $1 \le v_i \le 1000$

输入格式

第一行两个整数 $n\ m$ 接下来 $n$ 行，每行两个整数 $w_i\ v_i$，分别表示第 $i$ 个物品的重量和价值。

输出格式

输出答案

样例

样例一

输入

3 8
3 30
4 50
5 60

输出

90

样例二

输入

1 1000000000
1000000000 10

输出

10

样例三

输入

6 15
6 5
5 6
6 4
6 6
3 5
7 2

输出

17

数据范围与提示

• $1 < m < 10^9$
• $1 \le n \le 100$
• $1 \le w_i \le m$
• $1 \le v_i \le 1000$