C - お買い物チャレンジ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君はスーパーマーケットで買い物をしています。店内には N 個の商品が並んでおり、i 番目の商品（1 \leq i \leq N）には満足度 V_i と価格 C_i 円が定められています。各商品は最大 1 個まで購入できます。

高橋君の手持ちの金額は S 円です。高橋君は、この S 円をちょうど使い切りたいと考えています。

N 個の商品の中から 1 個以上を選んで購入することを考えます。選んだ商品の価格の合計がちょうど S 円となる選び方が存在するとき、そのような選び方すべての中での満足度の合計の最大値を求めてください。

価格の合計がちょうど S 円となる選び方が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 3000
  • 1 \leq S \leq 10000
  • 1 \leq V_i \leq 10000 (1 \leq i \leq N)
  • 1 \leq C_i \leq 10000 (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N S
V_1 C_1
V_2 C_2
\vdots
V_N C_N
  • 1 行目には、商品の個数を表す整数 N と、手持ちの金額を表す整数 S が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目の商品の満足度を表す整数 V_i と価格を表す整数 C_i が、スペース区切りで与えられる。

出力

価格の合計がちょうど S 円となるように商品を 1 個以上選ぶ方法が存在する場合、選んだ商品の満足度の合計の最大値を 1 行で出力してください。そのような選び方が存在しない場合は -1 を 1 行で出力してください。

入力例 1

3 5
3 2
4 3
1 4

出力例 1

7

入力例 2

3 10
1 3
2 3
3 3

出力例 2

-1

入力例 3

8 20
10 5
8 7
6 3
12 8
3 4
7 6
9 10
5 2

出力例 3

31

入力例 4

15 50
20 8
15 12
30 10
25 15
10 5
18 7
12 9
22 14
8 3
35 20
14 6
9 11
27 13
19 16
11 4

出力例 4

124

入力例 5

1 7
5 7

出力例 5

5

Score : 366 pts

Problem Statement

Takahashi is shopping at a supermarket. There are N items in the store, and the i-th item (1 \leq i \leq N) has a satisfaction value of V_i and a price of C_i yen. Each item can be purchased at most once.

Takahashi has S yen on hand. He wants to spend exactly S yen.

Consider selecting and purchasing 1 or more items from the N items. If there exists a way to select items such that the total price is exactly S yen, find the maximum total satisfaction among all such selections.

If no selection of items has a total price of exactly S yen, output -1.

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq S \leq 10000
  • 1 \leq V_i \leq 10000 (1 \leq i \leq N)
  • 1 \leq C_i \leq 10000 (1 \leq i \leq N)
  • All inputs are integers

Input

N S
V_1 C_1
V_2 C_2
\vdots
V_N C_N
  • The first line contains an integer N representing the number of items and an integer S representing the amount of money on hand, separated by a space.
  • The i-th line (1 \leq i \leq N) of the following N lines contains an integer V_i representing the satisfaction value and an integer C_i representing the price of the i-th item, separated by a space.

Output

If there exists a way to select 1 or more items such that the total price is exactly S yen, output the maximum total satisfaction of the selected items on a single line. If no such selection exists, output -1 on a single line.

Sample Input 1

3 5
3 2
4 3
1 4

Sample Output 1

7

Sample Input 2

3 10
1 3
2 3
3 3

Sample Output 2

-1

Sample Input 3

8 20
10 5
8 7
6 3
12 8
3 4
7 6
9 10
5 2

Sample Output 3

31

Sample Input 4

15 50
20 8
15 12
30 10
25 15
10 5
18 7
12 9
22 14
8 3
35 20
14 6
9 11
27 13
19 16
11 4

Sample Output 4

124

Sample Input 5

1 7
5 7

Sample Output 5

5