题目描述

あなたは $N$ 個の物と、強度 $W$ のバッグを持っています。 $i$ 個目の物は、重さが $w_i$ で価値が $v_i$ です。

あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は $W$ 以下でなくてはいけません。

あなたは、バッグに入れた物の価値の総和を最大化したいです。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ : $w_N$ $v_N$

输出格式

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

题目大意

你有 $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

4 6
2 1
3 4
4 10
3 4

11

4 6
2 1
3 7
4 10
3 6

13

4 10
1 100
1 100
1 100
1 100

400

4 1
10 100
10 100
10 100
10 100

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$ 個も物が選べません。