D - 背包 1（Knapsack 1）

**时间限制：**2 秒 **内存限制：**1024 MiB **分值：**100 分 ([atcoder.jp][1])

题目描述

有 (N) 件物品，编号为 (1,2,\ldots,N)。对于每件物品 (i)，它的重量为 (w_i)，价值为 (v_i)。

太郎准备从这 (N) 件物品中选出若干件，放入背包带回家。背包的容量为 (W)，也就是说，所选物品的重量总和不能超过 (W)。

请你求出太郎带回家的物品价值总和的最大值。

数据范围

• 输入中的所有数值均为整数。
• (1 \le N \le 100)
• (1 \le W \le 10^5)
• (1 \le w_i \le W)
• (1 \le v_i \le 10^9)

输入格式

输入从标准输入读入，格式如下：

N W
w_1 v_1
w_2 v_2
⋮
w_N v_N

输出格式

输出一个整数，表示太郎带回家的物品价值总和的最大值。

样例 1

输入

3 8
3 30
4 50
5 60

输出

90

说明

选择第 1 件和第 3 件物品。它们的重量总和为 (3+5=8)，价值总和为 (30+60=90)。

样例 2

输入

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

输出

5000000000

答案可能无法用 32 位整数类型表示。

样例 3

输入

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

输出

17

说明

选择第 2、4、5 件物品。它们的重量总和为 (5+6+3=14)，价值总和为 (6+6+5=17)。