问题 D: 打怪闯关(monster

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:175 通过:38

题目描述

小O正在玩一款打怪闯关的游戏。这款游戏一共有n关,小O需要按照顺序通过这 些关卡。初始小O有ℎ点血量。如果想通过第i关,需要先与第i关的boss战斗。这次战 斗会让小O降低ai点血量,如果战斗后小O的血量小于等于0,那么他就会闯关失败。 如果小O成功通过了第i关,那么它还会回复bi的血量。 小O为了通过这款游戏,准备了很多金币。使用一枚金币可以直接秒杀某一关的怪 兽,并且之后还可以获得该关卡的血量回复。小O想知道如果自己想通过,那么需要最 少花费多少枚金币?

【输入输出样例】

样例输入1

样例输出1

3 5

4 1

5 3

3 2

1

样例输入2

样例输出2

2 100

1 1

1 1

0


【数据范围约定】

对于10%的数据,n<=2

对于30%的数据n<=10;

对于另外30%的数据,bi=0;

对于90%的数据,n<=1000;

对于所有数据,1<=n<=10^5,1<=h<=10^4,0<=ai,bi<=10^4

输入格式

【输入格式】 第一行两个整数 n,ℎ; 接下来 n 行,每行两个整数ai,bi

输出格式

【输出格式】 一行一个整数,表示答案。

输入样例 复制

3 5
4 1
5 3
3 2

输出样例 复制

1

数据范围与提示

【样例解释】 0 对于样例1,小O会先挑战第一关的boss,血量降到1,然后回复1点血量,血量恢 复到2。然后花费1金币秒杀第二关的boss,回复3血量,血量回复到4。然后挑战第三 关的boss,血量降到1,然后回复2点血量,血量恢复到3。此时共花费一枚金币,挑战 成功