Clique on a Line

Given n points on a line with weights, two points are adjacent when their weights sum to at most their distance; find the largest clique.

Hard9Dynamic programmingSortingBinary searchGreedyNo attempts yetTime limit2sMemory limit512 MB

Problem

The clique problem is a well known NP-complete problem. The definition is short. Take an undirected graph GG and choose a subset CC of its vertices. If every pair of vertices in CC is joined by an edge, that is, if CC induces a complete graph, then CC is a clique. The clique problem asks for the size of the largest clique.

There are nn points on the xx axis, all at different coordinates. Point ii has coordinate xix_i and weight wiw_i. Build a graph on these points: two different points ii and jj are joined by an edge if and only if wi+wjxixjw_i + w_j \le |x_i - x_j|.

Find the size of the largest clique in that graph.

Input

The first line contains the number of points nn (1n2000001 \le n \le 200000).

Each of the next nn lines contains two integers xix_i and wiw_i (1xi,wi1091 \le x_i, w_i \le 10^9).

All xix_i are different.

Output

Print the size of the largest clique on the first line.