Chain Detonation

Interview

Time limit2sMemory limit512 MB

Summary

Place one extra bomb past the last one with unlimited power to destroy as many not-yet-detonated bombs, minimizing the duds among the original bombs.

Level: Medium6 of 10
Topics: Greedy, Intervals, Implementation
Solved: No attempts yet

Problem

A demolition crew placed $N$ bombs in a row. The bombs are numbered $1$ to $N$ from left to right. Bomb $i$ sits at coordinate $x_i$ and has destructive power $p_i$ .

Every timer was set to the same duration, but the crew planted the bombs starting from the right, so a bomb further to the right goes off slightly earlier. The detonation order is bomb $N$ , bomb $N-1$ , ..., bomb $1$ .

When bomb $i$ detonates, it destroys everything within distance $p_i$ to its left, that is, everything in the coordinate interval $[x_i - p_i,\ x_i]$ . Bombs that have not gone off yet are destroyed too. A destroyed bomb never detonates, and it counts as a dud.

To cut down on duds you plant one extra bomb. You may place it at any coordinate greater than $x_N$ and give it as much destructive power as you want, and it always detonates before every bomb that is already on the ground. Bombs destroyed by the extra bomb count as duds too. You may also place the extra bomb so that it destroys nothing.

Find the smallest number of duds you can end up with after planting one extra bomb.

Input

The first line contains the number of bombs $N$ ( $1 \le N \le 100000$ ).

Each of the next $N$ lines contains the coordinate $x_i$ ( $0 \le x_i \le 1000000$ ) and the destructive power $p_i$ ( $1 \le p_i \le 1000000$ ) of bomb $i$ , separated by a space. The coordinates are given in increasing order, so $x_1 < x_2 < \dots < x_N$ , and no two bombs share a coordinate.

Output

Print, on one line, the smallest number of duds that one extra bomb can leave.

Examples2

Example 1
Input
```
4
1 9
3 1
6 1
7 4
```
Expected output
```
1
```
Example 2
Input
```
7
1 1
2 1
3 1
4 1
5 1
6 1
7 1
```
Expected output
```
3
```