Шоссе будущего
В году 23413 Управление квантовыми дорогами (QRA) нуждается в вашей помощи для проектирования новой квантовой автомагистрали. Главное отличие квантовой автомагистрали от обычной заключается в том, что квантовые автомобили могут мгновенно менять полосы. То есть, в момент времени t_1 квантовый автомобиль может находиться на одной полосе, а в момент времени t_2 (где t_1 ≠ t_2) — уже на другой.
В году 23413 Управление прогнозирования будущего (FPA) располагает информацией о том, кто именно будет использовать эту новую автомагистраль. Для каждого квантового автомобиля, который будет двигаться по вашей квантовой автомагистрали, FPA предоставляет значение t, обозначающее время въезда автомобиля на автомагистраль, и значение v, представляющее скорость, с которой автомобиль будет двигаться.
Длина вашей автомагистрали составит 100 единиц. За одну единицу времени квантовый автомобиль, движущийся со скоростью v единиц, пройдет ровно v единиц длины. Размер квантового автомобиля незначителен по сравнению с длиной автомагистрали и рассматривается как точка.
Ваша задача — обеспечить отсутствие столкновений на этой квантовой автомагистрали. Квантовые автомобили оснащены сложными механизмами предотвращения столкновений: пока на автомагистрали достаточно полос, автомобили будут "волшебным образом" менять полосы, чтобы избежать столкновений. Столкновение происходит, если в любой момент времени количество автомобилей в определенной позиции на автомагистрали превышает количество полос. Такие столкновения могут произойти даже в начале или в конце автомагистрали, как показано в примерах.
Какое минимальное количество полос необходимо, чтобы избежать столкновений?
Входные данные
Для каждого теста:
Строка, содержащая одно целое число n (1 ≤ n ≤ 35000): количество квантовых автомобилей, которые будут двигаться по вашей автомагистрали.
n строк, содержащих два целых числа:
t_i : время, когда квантовый автомобиль i въезжает на вашу автомагистраль (1 ≤ t_i ≤ 10000).
v_i : скорость квантового автомобиля i (1 ≤ v_i ≤ 100).
Выходные данные
Для каждого теста выведите одну строку, содержащую одно целое число: количество полос, необходимых для предотвращения столкновений.