C - おやつ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは遠足に持って行くおやつを選んでいます。 この遠足には合計で P 円までのおやつを持って行くことができます。 ただし、担任のけんしょう先生はやさしいので、どの 1 つのおやつについても、そのおやつがなければ合計が P 円以下になるのであれば許してくれます。

例えば、100 円まで持って行くことができる時に、値段がそれぞれ 30 円、40 円、50 円のおやつを持って行くと、どの 1 つのおやつを取り除いても合計が 100 円以下になるので許してくれます。 しかし、40 円、50 円、60円のおやつを持って行くと、40 円のおやつがなかったとしても合計は 110 円となり 100 円を超えているので、やさしいけんしょう先生もこれは許してくれません。

高橋くんが持って行きたいおやつは N 種類あり、それぞれに値段と満足度があります。 高橋くんはそれぞれの種類のおやつについて最大でも 1 つしか遠足に持って行きません。 けんしょう先生が許してくれるおやつの選び方のうち、満足度の合計が最も大きくなるように選んだ時の満足度の合計を求めてください。

入力

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

N P
a_1 b_1
a_2 b_2
:
a_N b_N
  • 1 行目には、高橋くんが持って行きたいおやつの種類と合計で持っていけるおやつの金額を表す 2 つの整数 N, P (1 ≦ N ≦ 5,000, 1 ≦ P ≦ 5,000) が空白区切りで与えられる。
  • 2 行目からの N 行には高橋くんの持って行きたいそれぞれおやつの値段と満足度を表す整数 a_i b_i (1 ≦ a_i ≦ 100, 1 ≦ b_i ≦ 100) が空白区切りで与えられる。

部分点

この問題には部分点が設定されている。

  • 1 ≦ N ≦ 100, 1 ≦ P ≦ 100 を満たすデータセットに正解した場合は 50 点が与えられる。

出力

けんしょう先生が許してくれるおやつの選び方のうち、満足度の合計が最も大きくなるように選んだ時の満足度の合計を 1 行に出力せよ。

入力例1

4 100
30 50
40 40
50 100
60 80

出力例1

190

1 つ目と 2 つ目と 3 つ目のおやつを選ぶと満足度の合計が 190 となり、これがけんしょう先生が許してくれる選び方の中で最大である。

入力例2

5 100
40 10
30 50
60 80
20 40
20 70

出力例2

200

入力例3

10 654
76 54
62 19
8 5
29 75
28 4
76 16
96 24
79 30
20 64
23 56

出力例3

347

この入力は部分点に含まれない。