Задача C. Домино

Автор:Р. Данилов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Утконос Джордж очень любит домино. У него имеется N доминошек, которые он располагает вертикально вдоль координатной прямой. i —ая доминошка имеет координату xi и высоту hi. Все координаты xi строго возрастают. Бобер Саймон завидует Джорджу и понимает, что Джордж сильно расстроится, когда увидит, что какие-то его доминошки упали. Саймон может толкнуть ровно одну доминошку так, что она начнет падать в положительном направлении координатной прямой. При падении возникает цепная реакция: доминошка i толкнет доминошку i + k, если разница их координат не превосходит высоты i —ой доминошки.

Очевидно, что печаль Джорджа пропорциональна количеству упавших доминошек. Вы являетесь сторонним наблюдателем данной драмы и хотите узнать, какое максимальное количество доминошек может опрокинуть Саймон.

Формат входного файла

Первая строка входного файла содержит целое число N, количество доминошек.

Следующие N строк содержат по два числа xi, hi

Формат выходного файла

Выходной файл должен одно число — максимальное количество упавших доминошек.

Ограничения

1 ≤ N ≤ 105

1 ≤ xi, hi ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2
2 1
3 3
7 5
8 2
3
2
3
6 10
7 1
15 2
3
3
4
10 20
31 9
50 1
55 5
1

0.128s 0.017s 15