Description

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

Input Format

第一行两个整数n和h； 接下来n行，每行两个整数a_i和b_i。

Output Format

一行一个整数，表示答案。

3 5
4 1
5 3
3 2

1

Hint

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

【数据范围约定】 

对于10%的数据，n≤2 

对于30%的数据，n≤10 

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

对于90%的数据，n≤1000 

对于所有数据，1≤n≤10⁵,1≤h≤10⁴,0≤a_i,b_i≤10⁴

Source

2023绍兴小学组 贪心