403046: GYM100981 D Цветы

D. Цветыограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Вася хочет подарить Маше букет на 8 марта. Он знает одну тайную тропинку в лесу за городом, вдоль которой растут красивые, а главное, бесплатные цветы. Тропинка может быть представлена как прямая, причём можно считать, что Вася изначально появляется на ней в точке 0 и двигается со скоростью 1, не затрачивая времени на то, чтобы срывать цветы.

Цветок номер i растёт в точке тропинки с координатой x_i, а после того, как Вася его сорвёт, цветок остается живым еще t_i единиц времени. Естественно, Вася должен набрать в букет нечётное число цветов, и все они должны быть живыми в момент, когда он принесёт их в точку 0 на встречу с Машей (если i-й цветок принести ровно через t_i единиц времени после его срывания, то он уже не считается живым).

Вася — человек прямой, и даже ради Маши он не готов поворачивать (то есть менять направление своего движения вдоль тропинки) более 2 раз. Помогите ему собрать самый большой букет нечётного размера.

Входные данные

В первой строке входных данных вводится единственное целое число n (1 ≤ n ≤ 200 000) — количество цветов, растущих вдоль тропинки.

Каждая из следующих n строк содержит два целых числа x_i и t_i ( - 10⁹ ≤ x_i ≤ 10⁹, 0 ≤ t_i ≤ 10⁹) — координату i-го цветка и время, которое он будет живым, после того как его сорвут, соответственно. В одной точке может расти больше одного цветка.

Выходные данные

Выведите единственное число — максимально возможное количество цветов в букете. Если нельзя собрать букет даже из одного цветка, выведите 0.

ПримерыВходные данные

3
2 5
-1 2
3 4

Выходные данные

1

Входные данные

1
1 1

Выходные данные

0

Примечание

В первом примере можно сорвать два цветка, а именно пройти до точки 2 и взять цветок, который там растет, а затем пройти в точку  - 1 и сорвать цветок ещё и там. Но букеты из чётного количества цветков нам не подходят, поэтому ответ равен 1.

Во втором примере, если мы сорвем цветок и донесём его до точки 0, то пройдет как раз единица времени, и он завянет, поэтому букет собрать не получится.