题目描述

Farmer John's $N$ cows $(1 <= N <= 100,000)$ are out exercising their hooves again, jogging along an infinite track. Each cow starts at a distinct position on the track, and some cows run at different speeds.

The track is divided into lanes so that cows may move past each other. No two cows in the same lane may ever occupy the same position. Farmer John doesn't want any cow to have to change lanes or adjust speed, and he wonders how many lanes he will need to accomplish this if the cows are going to run for $T$ minutes $(1 <= T <= 1,000,000,000).$

输入格式

The first line of input contains $N$ and $T$.

The following $N$ lines each contain the initial position and speed of a single cow. Position is a nonnegative integer and speed is a positive integer; both numbers are at most 1 billion. All cows start at distinct positions, and these will be given in increasing order in the input.

输出格式

A single integer indicating the minimum number of lanes necessary so that no two cows in the same lane ever occupy the same location (including at time $T$).

题目大意

Farmer John 的 $N$ 头奶牛 $( 1 ≤ N ≤ 10^5 )$ 正在一条长度无限的跑道上慢跑，每头奶牛都有一个不同的开始位置，以及不同的跑步速度。

为了方便奶牛们互相超越，整个跑道被分成了若干条赛道。在同一时刻，不可能有在同一条赛道上的两头奶牛占据相同的位置。

现在奶牛们要跑 $T$ 分钟，在跑步过程中，他们不会改变自己所在的赛道和自己跑步的速度。FJ想要知道，为了奶牛间不会发生冲突，他需要至少准备多少条赛道。

输入格式：第一行包括两个整数 $N$ 和 $T$ 。接下来 $N$ 行，每行两个整数 $p_i$ 和 $v_i$ $( p_i , v_i ≤ 10^9 )$，分别代表奶牛的初始位置和速度。保证了初始位置不相同且为升序排列。

输出格式：一个整数，代表最少需要的跑道数目。

5 3
0 1
1 2
2 3
3 2
6 1

3