A9789 | Clique Problem

The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph $G$ . It is required to find a subset of vertices $C$ of the maximum size such that any two of them are connected by an edge in graph $G$ . Sounds simple, doesn't it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph.

Consider $n$ distinct points on a line. Let the $i$ -th point have the coordinate $x_{i}$ and weight $w_{i}$ . Let's form graph $G$ , whose vertices are these points and edges connect exactly the pairs of points $(i,j)$ , such that the distance between them is not less than the sum of their weights, or more formally: $|x_{i}-x_{j}|>=w_{i}+w_{j}$ .

Find the size of the maximum clique in such graph.

The first line contains the integer $n$ ( $1<=n<=200000$ ) — the number of points.

Each of the next $n$ lines contains two numbers $x_{i}$ , $w_{i}$ ( $0<=x_{i}<=10^{9},1<=w_{i}<=10^{9}$ ) — the coordinate and the weight of a point. All $x_{i}$ are different.

Print a single number — the number of vertexes in the maximum clique of the given graph.