AT_arc042_c [ARC042C] おやつ

[problemUrl]: https://atcoder.jp/contests/arc042/tasks/arc042_c 高橋くんは遠足に持って行くおやつを選んでいます。 この遠足には合計で $ 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 $ 行に出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 100,\ 1\ ≦\ P\ ≦\ 100 $ を満たすデータセットに正解した場合は $ 50 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ つ目と $ 2 $ つ目と $ 3 $ つ目のおやつを選ぶと満足度の合計が $ 190 $ となり、これがけんしょう先生が許してくれる選び方の中で最大である。 ### Sample Explanation 3 この入力は部分点に含まれない。