Problem D: Let's Go To School

Problem

がっちょ君は期末試験が近づくとやる気がなくなってしまい、しばしば学校を休むようになる。
期末試験まで残りN日である。
がっちょ君のi日目のやる気はX_iであり、i日目に学校に行くために必要なやる気はY_iである。
がっちょ君は X_i ≥ Y_i となる日のみ学校に行く。
がっちょ君を心配したハジ君は、がっちょ君を励ますことで、可能な限り学校に行かせようと考えた。
ハジ君は最初、励まし力Pを持っている。
ハジ君がi日目に励まし力t(tは0以上の任意の実数)を消費してがっちょ君を励ますと、 がっちょ君のi日目のやる気はtだけ増加して、ハジ君の励まし力はtだけ減少する。さらに、i+1 ≤ Nのとき、i+1日目のがっちょ君のやる気X_i+1はmax(0, X_i+1 − t) に変化する。
ハジ君は自分の持っている励まし力を超えて励ますことはできない。

ハジ君が最適な励まし方をしたときの、がっちょ君が学校に行く最大日数を求めよ。

Input

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

N P
X1 Y1
X2 Y2
...
XN YN

入力はすべて整数で与えられる。
1行目に期末試験までの日数Nとハジ君が最初に持っている励まし力Pが空白区切りで与えられる。
2行目から続くN行にはがっちょ君のi(i=1,2,...,N)日目のやる気X_iと学校に行くために必要なやる気Y_iが空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ N ≤ 100
• 0 ≤ P ≤ 10⁶
• 0 ≤ X_i ≤ 10⁶
• 0 ≤ Y_i ≤ 10⁶

Output

がっちょ君が学校に行くことができる最大の日数を1行に出力せよ。

Sample Input 1

3 10
1 6
5 10
0 5

Sample Output 1

2

Sample Input 2

5 5
1 1
1 2
1 2
1 3
1 3

Sample Output 2

4