No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Clique Problem

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

The first line contains the integer *n* (1 ≤ *n* ≤ 200 000) — 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.

Output

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

Examples

Input

4

2 3

3 1

6 1

0 2

Output

3

Note

If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars!

The picture for the sample test.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 02:41:27 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|