Lightning Rod

Time limit2.5sMemory limit512 MB

Summary

Given N buildings with tops at (X_i, Y_i), find the fewest buildings to place lightning rods on so that every building lies under a rod's 45-degree protection cone.

Level: Medium6 of 10
Topics: Stack, Greedy, Array
Solved: No attempts yet

Statement

Singapore has between 171 and 186 lightning days on average per year. Each square kilometer of land in Singapore can be struck up to 16 times annually, which makes Singapore one of the lightning capitals of the world.

Gug the architect surveys $N$ buildings from left to right. The top of building $i$ is at coordinates $(X_i, Y_i)$ . Gug wants to protect all the buildings by planting lightning rods on the tops of some buildings. A lightning rod protects the building it is planted on, along with every building that lies on or under the 45 degree line of depression going left and right from it. In other words, a lightning rod on building $i$ protects building $j$ if and only if $|X_i - X_j| \le Y_i - Y_j$ .

Find the minimum number of lightning rods needed to protect all buildings.

Input

The first line contains a single integer $N$ , the number of buildings. Each of the next $N$ lines contains two integers $X_i$ and $Y_i$ . It is given that $X_i \le X_{i+1}$ , so $X_i$ is non-decreasing.

The input is very large, so C++ fast input is needed to receive full credit.

Output

Print one integer, the minimum number of lightning rods required to protect all buildings.

Constraints

$2 \le N \le 10\,000\,000$

$0 \le X_i, Y_i \le 10^9$

Examples3

Example 1
Input
```
2
1 1
2 1
```
Expected output
```
2
```
Example 2
Input
```
2
1 0
2 1
```
Expected output
```
1
```
Example 3
Input
```
4
1 1
3 2
4 3
5 1
```
Expected output
```
2
```