/ XMU_ACM / 题库 /

集大校赛B-逃离蜂巢

集大校赛B-逃离蜂巢

Description

逃离蜂巢的过程中,Alice遇到了\(n\)个陷阱。
每个陷阱上有一瓶恢复药水,触发第\(i\)个陷阱可以先回复\(a_i\)点生命值(生命值没有上限),再受到\(b_i\)点伤害,触发完该陷阱就被拆除了,无法再次触发。
Alice的初始生命值为\(h\),任意时刻生命值都必须为正数。请问在她随意选择拆除顺序的情况下,最多可以拆除多少陷阱?

Format

Input

每个测试点仅包含一组输入数据。
第一行两个整数\(n,h(1<=n<=100000,1<=h<=10^9)\)。
接下来\(n\)行,第\(i\)行包含两个整数,表示\(a_i,b_i(1<=a_i,b_i<=10^9)\)。

Output

输出一行一个整数,表示最多可以拆除多少陷阱。

Sample 1

Input

2 5
10 8
1 4

Output

2

Limitation

1s, 1GB for each test case.

Source

Vijos Original

信息

ID
1096
难度
6
分类
(无)
标签
(无)
递交数
44
已通过
12
通过率
27%
上传者

相关