C - 8月31日 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

とある星のとある 8 月 31 日のことです。とある星の高橋君はあることに気づいてしまいました。今日で夏休みが終わりであるにもかかわらず、宿題が全く終わっていないのです！

宿題のタイムリミットまではあと T 分あります。そして、高橋君がやらなければいけない宿題は N 個あります。i 番目の宿題を高橋君が解くには A_i 分かかりますが、高橋君の友達である青木君が解いた宿題を丸写ししてしまうことで B_i 分で終わらせることもできます。しかし友達の宿題を写すのはあまり良くないことなので、高橋君はできるだけ写さないようにしたいと思っています。

タイムリミットまでに全ての宿題を終わらせるために高橋君が写す必要のある宿題の個数の最小値を出力してください。ただし、全ての宿題を写してもタイムリミットまでに終わらせることができない場合は代わりに -1 を出力してください。

入力

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

N T
A_1 B_1
A_2 B_2
:
A_N B_N
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), T (0 ≦ T ≦ 10^9) が空白区切りで与えられる。これは、宿題が N 個あり、タイムリミットまでの時間が T 分であることを表す。
  • 2 行目からの N 行には、宿題にかかる時間の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、2 つの整数 A_i, B_i (0 ≦ B_i < A_i ≦ 10^4) が空白区切りで与えられる。これは、i 番目の宿題を高橋君が解くと A_i 分かかり、写すと B_i 分かかることを表す。B_i < A_i であることに注意せよ。

部分点

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

  • B_i = 0 を満たすデータセットに正解した場合は、30 点が与えられる。
  • 追加の制約のないデータセットに正解した場合は、上記とは別に 70 点が与えられる。

出力

T 分以内に全ての宿題を終わらせるために高橋君が写す必要のある宿題の個数の最小値を 1 行に出力せよ。ただし、全ての宿題を写しても T 分以内に終わらせることができない場合は代わりに -1 を出力せよ。出力の末尾に改行を入れること。

入力例1

5 7
1 0
3 0
5 0
2 0
4 0

出力例1

2

例えば、2 番目と 3 番目の宿題を写せば 7(=1+0+0+2+4) 分で全ての宿題を終わらせることができます。

入力例2

1 1000000000
5 0

出力例2

0

宿題を写さなくてもタイムリミットに間に合います。

入力例3

1 0
100 99

出力例3

-1

宿題を写してもタイムリミットに間に合いません。

入力例4

3 11
5 2
6 4
7 3

出力例4

2

入力例5

6 92
31 4
15 9
26 5
35 8
97 9
32 3

出力例5

3