D - 冒険者の装備選び 解説 /

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

配点 : 400 点

問題文

高橋君は冒険者としてダンジョンに挑もうとしています。手持ちの装備品は全部で N 個あり、i 番目の装備品（i = 1, 2, \ldots, N）の防御力は W_i、攻撃力は S_i です。

今回挑むダンジョンは非常に危険で、身につけた装備品の防御力の合計が K 以上でなければ入場することができません。高橋君は N 個の装備品の中から 0 個以上 N 個以下の装備品を選んで身につけることができます。ただし、同じ装備品を 2 回以上選ぶことはできません。

高橋君は、選んだ装備品の防御力の合計が K 以上になるような選び方のうち、攻撃力の合計が最大となるようにしたいです。

防御力の合計が K 以上となる選び方が存在する場合は、攻撃力の合計の最大値を出力してください。そのような選び方が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 10^4
  • 1 \leq W_i \leq 10^4
  • 1 \leq S_i \leq 10^5
  • 入力はすべて整数である

入力

N K
W_1 S_1
W_2 S_2
\vdots
W_N S_N
  • 1 行目には、装備品の数 N と、必要な防御力の合計の下限 K が、スペース区切りで与えられる。
  • 続く N 行の i 行目（i = 1, 2, \ldots, N）には、i 番目の装備品の防御力 W_i と攻撃力 S_i が、スペース区切りで与えられる。

出力

防御力の合計が K 以上となる装備品の選び方が存在する場合は、攻撃力の合計の最大値を 1 行で出力せよ。存在しない場合は -1 を 1 行で出力せよ。

入力例 1

4 5
3 8
1 3
3 7
2 2

出力例 1

20

入力例 2

3 50
6 100
8 200
5 150

出力例 2

-1

入力例 3

10 30
5 80
1 10
8 90
4 50
6 70
3 40
2 30
7 60
9 50
10 50

出力例 3

530

Score : 400 pts

Problem Statement

Takahashi is an adventurer about to challenge a dungeon. He has a total of N pieces of equipment, where the i-th piece of equipment (i = 1, 2, \ldots, N) has a defense power of W_i and an attack power of S_i.

The dungeon he is about to challenge is extremely dangerous, and he cannot enter unless the total defense power of his equipped items is at least K. Takahashi can choose and equip anywhere from 0 to N pieces of equipment out of the N available. However, the same piece of equipment cannot be chosen more than once.

Among all ways to choose equipment such that the total defense power is at least K, Takahashi wants to maximize the total attack power.

If there exists a selection of equipment whose total defense power is at least K, output the maximum total attack power. If no such selection exists, output -1.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq 10^4
  • 1 \leq W_i \leq 10^4
  • 1 \leq S_i \leq 10^5
  • All input values are integers

Input

N K
W_1 S_1
W_2 S_2
\vdots
W_N S_N
  • The first line contains the number of pieces of equipment N and the minimum required total defense power K, separated by a space.
  • The following N lines each contain, on the i-th line (i = 1, 2, \ldots, N), the defense power W_i and attack power S_i of the i-th piece of equipment, separated by a space.

Output

If there exists a selection of equipment whose total defense power is at least K, output the maximum total attack power on a single line. If no such selection exists, output -1 on a single line.

Sample Input 1

4 5
3 8
1 3
3 7
2 2

Sample Output 1

20

Sample Input 2

3 50
6 100
8 200
5 150

Sample Output 2

-1

Sample Input 3

10 30
5 80
1 10
8 90
4 50
6 70
3 40
2 30
7 60
9 50
10 50

Sample Output 3

530