Problem1898--普及组模拟赛三B美食一条街

1898: 普及组模拟赛三B美食一条街

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

    小 S 的家乡有一条美食街,趁学习编程之余,小 S 出来逛逛,顺便吃点美食。
    美食街上共有 n 个店铺,第 i 个店铺的坐标位置在 xi,小 S 现在在美食街的入口处
(坐标位置为 0)。小 S 在街上移动的速度为 1(每单位时间)。即从位置 x1到 x2所耗
费的时间为|x1-x2|。
    由于各个店铺的美食不一样,所以在各店铺吃美食所耗费的时间也不相同,在第 i
个店铺吃美食耗费 ti个单位时间。小 S 比较注重个人形象,一般不会在路上边吃边走,
每个店铺的美食都会在店铺里面吃光。
    由于编程学习紧张,小 S 现在只有 m 个单位时间,请编程计算小 S 最多能在多少个
店铺吃美食。

Input

第一行包含两个整数 n,m。
接下来 n 行,每行包含两个整数 xi,ti。

Output

共一行包含一个整数,表示小 S 最多能吃美食的店铺数量。

Sample Input Copy

样例输入1:
3 9
1 100
5 2
3 3

样例输入2:
3 10
1 100
5 2
3 3

Sample Output Copy

样例输出1:1

样例输出2:2

HINT

数据范围


• 对于 30% 的数据, n ≤ 20。
• 对于 60% 的数据, n ≤ 1000。
• 对于 100% 的数据, 1 ≤ n ≤ 105, 0 ≤ m, xi ≤ 1018, 0 ≤ ti ≤ 109。


Source/Category