#AT5. Knapsack 2

Knapsack 2

[E] Knapsack 2(dp_e)

来源: AtCoder Educational DP Contest - Problem E 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 件物品,编号为 1,2,…,N1, 2, \ldots, N。

对于每个 ii(1≤i≤N1 \le i \le N),第 ii 件物品的重量为 wiw_i,价值为 viv_i。

太郎决定从中挑选若干件物品,装进背包带回家。背包的容量为 WW,即所选物品的重量之和不能超过 WW。

求太郎带回家的物品价值之和的最大值。

输入格式

输入由标准输入按以下格式给出:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

输出格式

输出太郎带回家的物品价值之和的最大值。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤1001 \le N \le 100
  • 1≤W≤1091 \le W \le 10^9
  • 1≤wi≤W1 \le w_i \le W
  • 1≤vi≤1031 \le v_i \le 10^3

样例 1

输入:

3 8
3 30
4 50
5 60

输出:

90

样例 2

输入:

1 1000000000
1000000000 10

输出:

10

样例 3

输入:

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

输出:

17