Home

Contest: Task: Related: TaskA TaskC

Score : $400$ points

Problem Statement

You have $N$ items and a bag of strength $W$. The $i$-th item has a weight of $w_i$ and a value of $v_i$.

You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most $W$.

Your objective is to maximize the total value of the selected items.

Constraints

  • $1 ≤ N ≤ 100$
  • $1 ≤ W ≤ 10^9$
  • $1 ≤ w_i ≤ 10^9$
  • For each $i = 2,3,...,N$, $w_1 ≤ w_i ≤ w_1 + 3$.
  • $1 ≤ v_i ≤ 10^7$
  • $W$, each $w_i$ and $v_i$ are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.

配点 : $400$ 点

問題文

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

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

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

制約

  • $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$ はすべて整数である

入力

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

$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

$1, 3$ 個目の物を選ぶと良いです。

入力例 2

4 6
2 1
3 7
4 10
3 6

出力例 2

13

$2, 4$ 個目の物を選ぶと良いです。

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