1838. 决斗(数据结构)

单点时限: 10.0 sec

内存限制: 256 MB

今天小强生日,结果不知趣的华师恶魔来挑衅,大家都知道小强是很强的,刚开始时,小强的魔力是 s,小强可以通过向其它魔法师学习,增强自己魔力。在小强请求第 i 个魔法师传授他魔法的时候,该魔法师会先考验哈利是不是有足够的根基,即足够的魔力 ni,如果小强的魔力不小于 ni,这个魔法师就会把自己所有的魔法传给小强,小强的魔力会增长 gi 因此小强以后就不用也没必要再向该魔法师请教。小强的最终目标是击败华师恶魔,由于时间有限,小强要在尽量少的学习次数里达到击败华师恶魔的最低魔力值 t。

输入格式

三个整数 n(0<=n<=100000),s(0<=s<=10000000),t(0<=t<=100000000),分别表示有 n 个魔法师可以让小强求教,小强的初始魔法值 s, 击败华师恶魔的最低魔力要求。

接下来 n 行每行两个整数 ni(0<=ni<=10000000),gi(0<=gi<=10000000),分别表示第 i 个魔法师对小强魔力的要求和能传授给哈利增加的魔力。

输出格式

输出小强最少要向多少个魔法师学习才能击败华师恶魔,如果小强最终不能击败华师恶魔,输出 “God helps xiaoqiang!” 不包括引号。

样例

Input
3 4 10
7 1
3 4
6 2
Output
2
Hint:在上面的情况,小强先找第二个法师学,魔力值为8,再向第三个法师学,魔力值达到10。

29 人解决,48 人已尝试。

36 份提交通过,共有 238 份提交。

5.5 EMB 奖励。

创建: 14 年,1 月前.

修改: 4 年,5 月前.

最后提交: 1 月,2 周前.

来源: N/A

题目标签