Шосе Майбутнього#7020

Шосе Майбутнього

1 секунда

64 мегабайти

Легка

Це рік 23413, і квантова дорожня адміністрація (QRA) потребує вашої допомоги у проектуванні нової квантової автомагістралі. Головна відмінність між квантовою автомагістраллю та звичайною полягає в тому, що квантові автомобілі можуть миттєво змінювати смугу. Тобто, в момент часу $t_{1}$ t_1 квантовий автомобіль може бути в одній смузі, а в момент $t_{2}$ t_2 (де $t_{1} \neq = t_{2}$ t_1 \ne t_2) — в іншій.

У році $23413$ адміністрація прогнозування майбутнього (FPA) вже знає, хто саме буде користуватися цією новою автомагістраллю. Для кожного квантового автомобіля, що подорожуватиме вашою квантовою автомагістраллю, FPA надає вам значення $t$ , яке є часом в'їзду автомобіля на автомагістраль, і значення $v$ , яке представляє швидкість руху автомобіля.

Довжина вашої автомагістралі становитиме $100$ одиниць. За одну одиницю часу квантовий автомобіль, що рухається зі швидкістю $v$ , проїде $v$ одиниць довжини. Розмір квантового автомобіля є незначним порівняно з довжиною автомагістралі; його слід вважати точкою.

Ваше завдання — забезпечити, щоб на цій квантовій автомагістралі не відбувалося зіткнень. Квантові автомобілі оснащені складними механізмами запобігання зіткненням: якщо на автомагістралі є достатньо смуг, автомобілі "магічно" змінюватимуть смуги, щоб уникнути зіткнень. Зіткнення відбувається, якщо в будь-який момент кількість автомобілів у певному положенні на автомагістралі перевищує кількість смуг. Такі зіткнення можуть статися навіть на самому початку або в кінці автомагістралі, як показують приклади.

Яка найменша кількість смуг потрібна, щоб уникнути зіткнень?

Вхідні дані

Для кожного тестового випадку:

Рядок, що містить одне ціле число $n$ ( $1 \leq n \leq 35000$ 1 \le n \le 35000): кількість квантових автомобілів, які подорожуватимуть вашою квантовою автомагістраллю.
$n$ рядків, що містять два цілі числа:
- $t_{i}$ t_i: час, коли квантовий автомобіль $i$ в'їжджає на вашу квантову автомагістраль ( $1 \leq t_{i} \leq 10000$ 1 \le t_i \le 10000).
- $v_{i}$ v_i: швидкість квантового автомобіля $i$ ( $1 \leq v_{i} \leq 100$ 1 \le v_i \le 100).

Вихідні дані

Для кожного тестового випадку виведіть один рядок, що містить одне ціле число: кількість смуг, необхідних для того, щоб уникнути зіткнень.

Приклади

Приклад 1