## Dominoes

Farmer John's son, 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 one-dimensional 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 pushed to the right, will knock all dominoes at positions x+1, x+2, ..., x+h rightward as well.
Conversely, the same domino pushed to the left will knock all dominoes at positions x-1, x-2, ..., x-h leftward.

### Input

The input starts with a single integer N ≤ 100,000, the number of dominoes, followed by N pairs of integers.
Each pair of integers represents the location and height of a domino.
(1 ≤ location ≤ 1,000,000,000, 1 ≤ height ≤ 1,000,000,000)
No two dominoes will be in the same location.

NOTE: 60% of test data has N ≤ 5000.

### Output

One line, with the number of pushes required.

### Sample Input

```6 1 1 2 2 3 1 5 1 6 1 8 3```

### Sample Output

`2`

Push the domino at location 1 rightward, the domino at location 8 leftward.

### Diagram

```              |
|           |
| | |   | |   |
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.

Point Value: 25
Time Limit: 1.00s
Memory Limit: 64M
Added: Sep 26, 2008
Author: hansonw1

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (0/0)
Try solving it in O(n^2) complexity, then you can convert it to O(N*LOG(N)) using Data structure.

• (2/0)
The dominos aren't sorted by position.

• (7/1)
Make a recursive function f(n) that gives the minimum # of moves required to topple the first n dominoes.

Now how do you relate f(n) to previous values of f?
Domino #n has two choices: go left (in which case it topples other dominoes over) or go right
(in which case another domino to its left topples it over). Try working from there.