403046: GYM100981 D Цветы

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

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

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

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

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

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

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

ПримерыВходные данные
3
2 5
-1 2
3 4
Выходные данные
1
Входные данные
1
1 1
Выходные данные
0
Примечание

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

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

加入题单

上一题 下一题 算法标签: