Cow Jog

Interview

Time limit1sMemory limit256 MB

Summary

Count the groups of cows that end at the same position after T minutes when no cow can pass the cow ahead.

Level: Medium5 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

The cows are out exercising their hooves again. $N$ cows are jogging on an infinitely long single-lane track ( $1 \le N \le 100\,000$ ). Every cow starts at a different position, and some cows jog at different speeds.

The track has only one lane, so a cow cannot pass the cow ahead of her. When a faster cow catches up to the cow ahead, she slows down to avoid running into her and becomes part of the same group.

The cows run for $T$ minutes ( $1 \le T \le 10^9$ ). Determine how many groups are left at that point. Two cows count as the same group if they are at the same position at the end of the $T$ minutes.

Input

The first line contains the two integers $N$ and $T$ .

Each of the next $N$ lines contains the starting position and the speed of one cow. The position is a nonnegative integer and the speed is a positive integer, and both are at most 1 billion. All cows start at different positions, and the positions are given in increasing order.

Output

Print a single integer, the number of groups that remain after $T$ minutes.

Examples4

Example 1
Input
```
5 3
0 1
1 2
2 3
3 2
6 1
```
Expected output
```
3
```
Example 2
Input
```
1 1000000000
0 1000000000
```
Expected output
```
1
```
Example 3
Input
```
4 1000000000
0 5
1 5
2 5
3 5
```
Expected output
```
4
```
Example 4
Input
```
3 1000000000
0 3
1 2
2 1
```
Expected output
```
1
```