Problem
Ghiaccio wants to walk the streets of Venice. However, today he is quite irritable, which makes it difficult to walk.
Venice is quite a popular city among tourists, who, however, call the city "Venice" in a foreign manner, instead of the correct "Venezia".
This makes Ghiaccio very angry, but he does not want to remain furious after the walk. Therefore, he decided that sometimes he would plug his ears when passing by tourists so as not to get angry again.
Ghiaccio has an internal calmness bar that replenishes by one point per second (when Ghiaccio leaves the house, the value of this bar is zero).
However, if Ghiaccio passes by a tourist group, in which there are d people, then his calmness decreases by d, because he gets angry at the mispronunciation of the city's name. But if Ghiaccio walks by, plugging his ears, his calmness will not diminish.
If at some point in time the calm scale becomes negative, then Ghiaccio will go berserk, which is extremely unacceptable.
Ghiaccio knows Venice very well, so he knows that during the walk he will pass about n tourist groups, for each of which it is known that it will be in the second with the number t
i and in this group there will be d< sub>i people.
Based on this information, calculate the minimum number of times Ghiaccio will have to plug his ears so that he does not go berserk while walking.
Input:
The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of tourist groups around which Ghiaccio will pass.
Then n lines follow, each containing two space-separated integers: t
i and d
i (1 ≤ t
i , d
i ≤ 10
9) — the number of the second in which Ghiaccio will pass by the i-th tourist group, and the number of people in it. All t
i are distinct and are in ascending order.
Output:
Print a single integer — the minimum number of times Ghiaccio will have to plug his ears in order not to go berserk.
Examples:
| Input |
Output |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Explanations:
In the first example, Ghiaccio has to plug his ears while passing near the second group.
Then by the end of the third second, his calmness will be equal to 1 (3 he made up for every second of the walk, but decreased by 2 passing by the first group).
By the end of the fifth second, calmness will be equal to 3 (calmness will not decrease from the second group, because Ghiaccio plugged his ears as he passed).
And by the end of the sixth second, the calmness will be equal to 3+1-3 = 1.
Further, his calmness never diminishes.