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.

提交代码