N (1 <= N <= 100,000) коров фермера Джона бегут по бесконечной
трассе. Все коровы начинают в различных позициях и некоторые
коровы бегут с различной скоростью.
Трасса поделена на дорожки, поэтому коровы могут обгонять друг
друга. Никакие две коровы на одной и той же дорожке не могут
занимать одну и ту же позицию.
Фермер Джон хочет, чтобы никакая корова не меняла свою дорожку
или изменяла свою скорость. И он интересуется, сколько дорожек
ему нужно, если коровы будут бежать T минут (1 <= T <= 1,000,000,000).
Формат входных данных
Первая строка ввода содержит N и T.
Каждая из последующих N строк содержит начальную позицию и скорость
одной коровы. Позиция - это неотрицательное целое число, а скорость -
положительное целое число, оба не более 1 миллиарда. Все коровы начинают
в различных позициях, заданных в порядке возрастания на вводе.
Формат выходных данных
Одно целое число, указывающее минимальное количество дорожек,
необходимое, чтобы никакие две коровы не занимали на одной и той же
дорожке одну и ту же позицию в течение времени T (включительно).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
0 1
1 2
2 3
3 2
6 1
|
3
|