Advertisement 2

Interview

Time limit2sMemory limit1024 MB

Summary

Given each resident's coordinate and influence power, find the fewest residents to donate copies to so that everyone ends up with a copy.

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

Problem

There are $N$ residents in JOI Kingdom, numbered from $1$ to $N$ . Resident $i$ ( $1 \le i \le N$ ) lives at the coordinate $X_i$ on the real line, and its power of influence is $E_i$ . More than one resident may live at the same coordinate. A resident with a large power of influence has high advertising potential, but such a resident is careful about buying books.

Rie published a book on informatics. To encourage many people to buy copies, she can donate copies of the book to some residents. If she donates a copy to Resident $i$ ( $1 \le i \le N$ ), Resident $i$ gets a copy. Then, among the residents who did not yet get a copy, every resident $j$ ( $1 \le j \le N$ ) satisfying the following condition buys a copy and gets it.

$|X_i - X_j| \le E_i - E_j$

If all the residents read Rie's book, the Olympiads in Informatics will be greatly recognized. Write a program that calculates the minimum number of residents who must be donated copies so that all the residents get a copy of Rie's book.

Input

Read the following data from the standard input.

N
X_1 E_1
X_2 E_2
\vdots
X_N E_N

Output

Write one line to the standard output. The line contains the minimum number of residents who must be donated copies of Rie's book.

Constraints

$1 \le N \le 500\,000$ .
$1 \le X_i \le 10^9$ ( $1 \le i \le N$ ).
$1 \le E_i \le 10^9$ ( $1 \le i \le N$ ).
All given values are integers.

Examples3

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

Example 3

Input

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

Expected output