DOMINOES  Dominoes
Johnny is playing with some dominoes one afternoon. His dominoes come in a variety of heights and colors.
Just like any other child, he likes to put them in a row and knock them over.
He wants to know something: how many pushes does it take to knock down all the dominoes?
Johnny is lazy, so he wants to minimize the number of pushes he takes.
A domino, once knocked over, will knock over any domino that it touches on the way down.
For the sake of simplicity, imagine the floor as a onedimensional line, where 1 is the leftmost point. Dominoes will not slip along the floor once toppled. Also, dominoes do have some width: a domino of length 1 at position 1 can knock over a domino at position 2.
For the mathematically minded:
A domino at position x with height h, once knocked over to the right, will knock all dominoes at positions x+1, x+2, ..., x+h rightward as well.
Similarly, the same domino knocked over to the left will knock all dominoes at positions x1, x2, ..., xh leftward.
Input
The input starts with a single integer N (N ≤ 100000), the number of dominoes, followed by N pairs of integers.
Each pair of integers represents the location and height of a domino, in that order (0 ≤ location ≤ 10^{9}, 0 ≤ height ≤ 10^{9}).
No two dominoes will have the same location.
Output
A single integer on a single line: the minimum number of pushes Johnny must make in order to ensure that all dominoes are knocked over.
Example
Input: 6 1 1 2 2 3 1 5 1 6 1 8 3 Output: 2 Explanation          1 2 3 4 5 6 7 8
Pushing 1 causes 2 and 3 to fall, while pushing 8 causes 6 to fall and gently makes 5 tip over as well.
hide comments
Aditya Muraletharan:
20130117 18:24:50
Excellent problem:)


rahul singal:
20110531 13:12:06
what does h==0 mean ?? should a domino be pushed at this position ? 

Brian Bi:
20091213 18:53:39
hmm, you are right, sorry about that (*sigh* again it's Hanson's test data but I really should've checked it before uploading it) 

Abir:
20091213 18:53:39
I sent a checker and found that input data contains height = 0. 
Added by:  Brian Bi 
Date:  20090410 
Time limit:  0.104s0.251s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS PERL6 VB.NET 
Resource:  Hanson Wang 