Cow Jog

Time limit1sMemory limit256 MB

Summary

Cows start in fixed order with fixed speeds, and you assign the fewest lanes so no two cows in one lane ever meet by time T.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Greedy
Solved: No attempts yet

Problem

Farmer John's $N$ cows are jogging along an infinite track. Cow $i$ starts at position $x_i$ and runs in the same direction at a constant speed of $v_i$ per minute. All starting positions are distinct.

The track is divided into lanes, so cows in different lanes may move past each other. No two cows in the same lane may ever occupy the same position. Farmer John does not want any cow to change lanes or adjust its speed.

The cows run for $T$ minutes. Find the minimum number of lanes he needs. Times from $0$ to $T$ count, including time $T$ itself.

Input

The first line contains the number of cows $N$ and the running time $T$ . ( $1 \le N \le 10^5$ , $1 \le T \le 10^9$ )

Each of the next $N$ lines contains the starting position $x_i$ and the speed $v_i$ of one cow. $x_i$ is a nonnegative integer at most $10^9$ , and $v_i$ is a positive integer at most $10^9$ . All starting positions are distinct and are given in increasing order.

Output

Print one line with the minimum number of lanes needed so that no two cows in the same lane ever occupy the same position up to time $T$ .

Examples2

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