ZOJ Problem Set - 3617
After killing YanLiang and WenChou, GuanYu gets the news that his brother LiuBei is still alive. So GuanYu decides to escape from CaoCao and go to the place where LiuBei is. But as we know, CaoCao always thinks highly of GuanYu, so he is very angry when he knows that GuanYu has escaped. And he commands all the toll-gates to stop GuanYu. Therefore it seems that it is not easy for GuanYu to escape.
To get to the destination, GuanYu needs to pass n toll-gates in order. And CaoCao is so good to GuanYu that GuanYu knows lots of informations of the toll-gates. GuanYu knows that enemies in each toll-gate will try to stop GuanYu and GuanYu will lose xi hp if he wants to pass the i-th toll-gate. And GuanYu has a maximum hp max, and he has full hp at the beginning. If GuanYu's hp is equal to or lower than 0, he will died unfortunately.
Luckily, GuanYu also know that he can restore ai hp if he have a rest at the i-th toll-gate for a unit time(of course he needs to pass the toll-gate first). And he can rest at a toll-gate for as long time as he wants.But GuanYu is eager to go to the destination, and there are a lot of enemies behind him. So he can't waste too much time. Please help GuanYu to calculate the minimum time GuanYu needs to rest.
You should notice that GuanYu isn't clever enough so he can only have a rest for integer time. And GuanYu'hp can't be more than max, and the amount exceeded will vanish. And you can assume that GuanYu is so powerful that he will finally pass all the toll-gates if he gets enough rest.
There are multiple cases. Each case consists of n+1 lines. The first line has a positive integer n(n ≤ 100000), which represents for the number of toll-gates GuanYu needs to pass, and a positive integer max(max ≤ 10000000), which represents the toplimit of GuanYu's hp. The next n lines consists of two integers xi and ai which have mentioned above(0 < ai,xi ≤ 10000000).
For each case, output a single line containing exactly one integer which represent for the minimum time GuanYu needs to rest.
5 12 4 4 5 2 1 5 3 6 9 1
Author: ZHANG, Ruijie
Contest: ZOJ Monthly, June 2012