Description

There are $N$ cows jogging on an infinitely long single-lane track, where $1 \le N \le 100000$. Each cow starts at a distinct position on the track, and some cows jog at different speeds.

Since the track has only one lane, cows cannot pass each other. When a faster cow catches up to a slower cow, she must slow down to avoid running into her, becoming part of the same running group.

The cows will run for $T$ minutes, where $1 \le T \le 1000000000$. Please determine how many groups remain at that time. Two cows are considered part of the same group if they are at the same position at the end of $T$ minutes.

Input Format

• The first line contains two integers $N$ and $T$.
• Each of the following $N$ lines contains two integers: the initial position and speed of a single cow. The position is a nonnegative integer and the speed is a positive integer; both are at most $10^9$. All cows start at distinct positions, given in increasing order.

Output Format

Output a single integer indicating how many groups remain after $T$ minutes.

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

 

 

3 

 

Hint

Translated by ChatGPT 5