3207 - 物理实验

题目描述

科学家发现了一种新粒子,于是将 N 个新粒子放到一条笔直的粒子试验机中进行实验。

科学家将这 N 个粒子放在了 N 个不同的位置上,并给每个粒子设置初始速度,让所有粒子同时向右以初始速度匀速移动。假设第 i 个粒子的初始速度为 V_i ,那么理论上该粒子每过 1 秒会向右移动 V_i 个单位的距离。

实验中,科学家观察到一个有趣的现象,当速度更快的粒子追上速度较慢的粒子时,速度更快的粒子会立刻把自己的速度降低到与其追上的粒子相等的速度,和该粒子“组成一队”,一起匀速右移。

可以预测,随着时间的推移,可能会有很多粒子一起组队并肩前行。

请编程计算出,在第 T 秒,“组成一队”的粒子,共有多少个队伍?即,如果将在同一个位置的粒子计算为一个队伍,请你编程计算出队伍的总数量。

输入

1 行输入两个整数 N,T

接下来 N 行,每行给出两个整数,第 i 行的两个整数 P_i,V_i 分别代表第 i 个粒子的初始位置和初始速度。

测试数据确保所有粒子的初始位置不同,且初始位置保证升序给出。

输出

输出一个整数,代表在第 T 秒,粒子形成的队伍的总数量。

样例

输入

5 3
0 9
2 1
4 10
5 9
9 9

输出

3

输入

8 10
0 4
2 18
3 10
8 8
9 4
11 11
12 2
13 4

输出

2

输入

20 100
1 2
2 12
3 28
4 10
5 27
10 10
11 2
12 18
13 10
14 6
15 25
16 8
17 7
18 9
19 25
20 18
21 11
22 7
24 6
25 12

输出

5
说明

样例 1 解释

3 秒时,第 1 和第 2 个点形成一个队伍,第 3 个点和第 4 个点形成一个队伍,第 5 个点单独形成一个队伍。

因此共有 3 个队伍。

数据范围

对于 40\% 的数据,1 \le N \le 1001 \le T \le 300

对于 100\% 的数据,1 \le N \le 10^51 \le T \le 10^90 \le P_i \le 10^91 \le V_i \le 10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 281
通过人数 95
金币数量 0 枚
难度 基础


上一题 下一题