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