Hanyang Popularity Exceeding Competition

Time limit1sMemory limit1024 MB

Summary

Pick a subsequence of celebrities to meet in order, where each meeting adds 1 only if |P-X| is at most C. Find the maximum final popularity.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Hanyang University has held the Hanyang Popularity Exceeding Competition since 2023. The contest runs for a set period, and the student with the highest popularity when it ends wins. Cheolmin is a contestant, but he has just started school, so his popularity is $0$ .

Cheolmin made a plan to win by meeting $N$ celebrities of Hanyang University. He will meet them in order, from celebrity 1 to celebrity $N$ .

Real life is more complicated. Meeting a celebrity does not always raise popularity. If one side's fame is far higher than the other's, the higher side drowns out the other. Precisely, let Cheolmin's current popularity be $X$ , celebrity $i$ 's popularity $P_i$ , and affinity $C_i$ . If $|P_i-X|\le C_i$ , Cheolmin's popularity increases by $1$ . If $|P_i-X|>C_i$ , his popularity does not change.

Instead of meeting all celebrities, Cheolmin picks some of them to meet and tries to maximize his popularity. What is the maximum popularity Cheolmin can reach?

The celebrities are busy, so the meeting times cannot be changed. In other words, Cheolmin cannot change the plan to meet a higher-numbered celebrity first.

Input

The first line contains $N$ , the number of celebrities at Hanyang University. ( $1\le N\le 200\,000$ )

Each of the next $N$ lines contains two integers $P_i$ and $C_i$ , the popularity and affinity of celebrity $i$ , separated by a space. ( $0\le P_i,C_i\le 500$ )

Output

Print the maximum popularity Cheolmin can reach on the first line.

Examples3

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