#K7601. Maximum Communication Towers

    ID: 34547 Type: Default 1000ms 256MiB

Maximum Communication Towers

Maximum Communication Towers

You are given n towers on a one-dimensional line. Each tower is described by two integers: its position x and its signal range r. The signal of a tower covers the interval \( [x - r,\; x + r] \). Two towers can communicate with each other if the right endpoint of one tower's range is no less than the left endpoint of the other tower's range.

Your task is to select a subset of towers such that for any two consecutive towers in your chosen order (after sorting by position), the following condition holds:

\( x_j + r_j \ge x_i - r_i \) for any tower \( j \) chosen before tower \( i \).

Determine the maximum number of towers that can simultaneously communicate with each other.

Note: The input is given through stdin and the output should be printed to stdout.

inputFormat

The first line contains an integer \( n \) representing the number of towers.

Each of the following \( n \) lines contains two integers \( x \) and \( r \) separated by a space, indicating the position and signal range of a tower, respectively.

\( 1 \le n \le 10^5 \) (for the given problem size, a quadratic algorithm is acceptable for small \( n \)).

outputFormat

Output a single integer representing the maximum number of towers that can communicate with each other.

## sample
4
1 2
2 1
5 1
10 2
2