County Fair Events

Time limit2sMemory limit512 MB

Summary

Given N intervals, find the maximum number of non-overlapping intervals John can attend.

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

Problem

Farmer John is back at the county fair, where $N$ special events are held: concerts, rodeos, cooking shows, and the like. He wants to attend as many of them as he can.

He rented a bicycle, so moving from one event to the next takes no time at all.

Event $i$ starts at time $T_i$ and runs for $L_i$ time units, so it ends at time $T_i + L_i$ . John never leaves an event early, so attending an event means staying from its start to its end. If one event ends at the same moment another starts, he can attend both.

Determine the largest number of events John can attend.

Input

The first line contains the number of events $N$ ( $1 \le N \le 10000$ ).

Each of the next $N$ lines contains two integers $T$ and $L$ separated by a space, the start time and the duration of one event ( $1 \le T \le 100000$ , $1 \le L \le 100000$ ).

Output

Print on the first line the largest number of events John can attend.

Examples5

Example 1
Input
```
7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
```
Expected output
```
4
```
Example 2
Input
```
1
1 1
```
Expected output
```
1
```

Example 3

Input

Expected output

Example 4
Input
```
4
1 3
4 2
6 5
11 1
```
Expected output
```
4
```
Example 5
Input
```
5
1 20
1 4
5 4
9 4
13 4
```
Expected output
```
4
```