#5438. Problem 3. Cow Jog

0

Problem 3. Cow Jog

好的,这是您提供的 USACO 2014 年 12 月竞赛 Gold 组第三题 Cow Jog 的中文翻译:


问题 3. 牛的慢跑 (Cow Jog)

USACO 2014 年 12 月竞赛,Gold 组

农夫约翰的 NN 头奶牛(1N100,0001 \le N \le 100,000)正在跑道上锻炼蹄子。每头牛都从跑道上一个不同的初始位置开始,并且有些奶牛以不同的速度奔跑。

跑道被分成若干车道,以便奶牛可以相互超越。同一车道内的奶牛任何时刻都不能占据相同的位置。农夫约翰不希望任何奶牛需要改变车道或调整速度,因此他想知道,如果奶牛们要奔跑 TT 分钟(1T1,000,000,0001 \le T \le 1,000,000,000),他至少需要多少条车道才能满足要求。

输入 (文件 cowjog.in):

第一行包含 NNTT

接下来的 NN 行,每行包含一头奶牛的初始位置速度。位置是非负整数,速度是正整数;这两个数字都不超过 10 亿。所有奶牛的初始位置都不同,并且输入中的位置是按递增顺序给出的。

输出 (文件 cowjog.out):

一个单独的整数,表示完成此任务所需的最小车道数,使得同一车道内的任意两头牛在任何时刻(包括时间 TT 时)都不会占据相同的位置

示例输入:

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

示例输出:

3