[ABC060D] Simple Knapsack

题意翻译

你有 $N$ 个物品和容量为 $W$ 的背包,每个物品要么选要么不选,它们的体积为 $w_i$,价值为 $v_i$,求总体积至多为 $W$ 情况下能拿走物品价值的最大值。 **【数据范围】** $1\le N \le 100$,$1\le W \le 10^9$,$1 \le w_i \le 10^9$ $w_1 \le w_i \le w_1+3 (i=2,3,\cdots N)$ $1 \le v_i \le 10^7$ $W,w_i,v_i$ 都是整数 翻译:[So_what](https://www.luogu.org/space/show?uid=68706)

题目描述

[problemUrl]: https://atcoder.jp/contests/abc060/tasks/arc073_b あなたは $ N $ 個の物と、強度 $ W $ のバッグを持っています。 $ i $ 個目の物は、重さが $ w_i $ で価値が $ v_i $ です。 あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は $ W $ 以下でなくてはいけません。 あなたは、バッグに入れた物の価値の総和を最大化したいです。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ : $ w_N $ $ v_N $

输出格式


価値の総和の最大値を出力する。

输入输出样例

输入样例 #1

4 6
2 1
3 4
4 10
3 4

输出样例 #1

11

输入样例 #2

4 6
2 1
3 7
4 10
3 6

输出样例 #2

13

输入样例 #3

4 10
1 100
1 100
1 100
1 100

输出样例 #3

400

输入样例 #4

4 1
10 100
10 100
10 100
10 100

输出样例 #4

0

说明

### 制約 - $ 1\ ≦\ N\ ≦\ 100 $ - $ 1\ ≦\ W\ ≦\ 10^9 $ - $ 1\ ≦\ w_i\ ≦\ 10^9 $ - すべての $ i\ =\ 2,3,...,N $ について、$ w_1\ ≦\ w_i\ ≦\ w_1\ +\ 3 $ - $ 1\ ≦\ v_i\ ≦\ 10^7 $ - $ W,\ w_i,\ v_i $ はすべて整数である ### Sample Explanation 1 $ 1,\ 3 $ 個目の物を選ぶと良いです。 ### Sample Explanation 2 $ 2,\ 4 $ 個目の物を選ぶと良いです。 ### Sample Explanation 3 すべての物が選べます。 ### Sample Explanation 4 $ 1 $ 個も物が選べません。