Minimum Lightning Rod Installations

Consider the skyline of Singapore represented in a 2D Cartesian coordinate system. The top of the i-th building is given by the point \((X_i, Y_i)\). A lightning rod installed on the top of a building protects a region defined by two rays making \(45^\circ\) angles with the coordinate axes, extending downward left and downward right from that building. In other words, if a lightning rod is installed on building \(i\), it protects exactly those buildings \(j\) that satisfy the condition:

[ |X_i - X_j| \le Y_i - Y_j ]

Note that this inequality is only meaningful if \(Y_i \ge Y_j\). Your task is to determine the minimum number of lightning rods that must be installed so that every building is protected by at least one rod.

Observation: If a rod is installed on a building \(i\) (with \(P_i = X_i+Y_i\) and \(Q_i = X_i-Y_i\)), then it can protect a building \(j\) (with \(P_j = X_j+Y_j\) and \(Q_j = X_j-Y_j\)) if and only if:

[ P_i \ge P_j \quad \text{and} \quad Q_i \le Q_j ]

A greedy strategy can be applied by sorting the buildings by \(Q = X-Y\) in ascending order and keeping track of the smallest \(P = X+Y\) among the selected lightning rods. A building is covered if its \(P\) is less than or equal to the last chosen rod’s \(P\); otherwise, a new rod must be installed at that building.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) denoting the number of buildings. Each of the following \(n\) lines contains two integers \(X_i\) and \(Y_i\) (\(0 \le X_i, Y_i \le 10^9\)) representing the coordinates of the top of the i-th building.

outputFormat

Output a single integer representing the minimum number of lightning rods needed so that every building is protected.

sample

2
1 1
2 2

2