Маленькая девочка Сьюзи каждый день слушает сказки перед сном. Сегодняшняя сказка была про дровосеков, поэтому маленькая девочка сразу же начала представлять себе, как дровосеки рубят деревья, и в её мыслях родилась ситуация, описанная ниже.
Есть n деревьев, расположенных вдоль дороги в точках с координатами x1, x2, ... , xn. Каждое дерево имеет свою высоту hi. Дерево можно срубить и повалить влево или вправо. Тогда оно будет занимать отрезки [xi - hi, xi] и [xi;xi + hi] соответственно. Пока дерево не срублено, оно занимает точку с координатами xi. Дерево можно повалить, если на отрезке, который оно должно занимать после сваливания, нет ни одной занятой точки. Дровосеки хотят заготовить как можно большее число деревьев, поэтому Сьюзи стало интересно, какое наибольшее количество деревьев можно повалить.
Выходные данные
Требуется вывести одно число — максимальное количество деревьев, которое можно срубить по указанным правилам.
Примечание
В первом примере деревья можно повалить так:
- повалить 1-е дерево влево — теперь оно занимает отрезок [ - 1;1]
- повалить 2-е дерево вправо — теперь оно занимает отрезок [2;3]
- оставить 3-е дерево — оно занимает точку 5
- оставить 4-е дерево — оно занимает точку 10
- повалить 5-е дерево вправо — теперь оно занимает отрезок [19;20]
Во втором примере можно повалить еще и 4 дерево вправо, после чего оно займет отрезок [10;19].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
2 1
5 10
10 9
19 1
|
3
|
|
2
|
5
1 2
2 1
5 10
10 9
20 1
|
4
|