Задача о клике — одна из самых известных NP-полных задач. После некоторых оговорок она формулируется следующим образом. Рассмотрим неориентированный граф G. Требуется найти такое подмножество вершин C максимального размера, что любые две из них соединены ребром в графе G. Звучит просто, не правда ли? К текущему моменту не известен алгоритм, который находит решение этой задачи за полиномиальное время от размера графа. Однако, как и в случае многих других NP-полных задач, задача о клике оказывается проще, если рассмотреть граф специфического вида.
Рассмотрим n различных точек на прямой. Пусть i-я точка имеет координату xi и вес wi. Образуем граф G, вершинами которого являются эти точки, а рёбрами соединены в точности те пары точек (i, j), для которых расстояние между этими точками не меньше суммы их весов, формально говоря: |xi - xj| ≥ wi + wj.
Найдите размер максимальной клики в таком графе.
Выходные данные
Выведите одно число — количество вершин в максимальной клике образованного графа.
Примечание
Если вы вдруг умеете решать эту задачу, не используя специфические свойства графа, представленного в условии задачи, то вам полагается приз в миллион доллларов!
Изображение к тесту из условия:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3
3 1
6 1
0 2
|
3
|