Minimum Lane Assignment for Jogging Cows

Farmer John's N cows \( (1 \le N \le 100,000) \) are out exercising their hooves along an infinite track. Each cow starts at a distinct position and runs at a constant speed. They will run for \(T\) minutes \( (1 \le T \le 1,000,000,000) \). The track is divided into lanes so that cows may pass each other, but no two cows in the same lane may ever occupy the same position.

For each cow \(i\), let \(x_i\) denote its starting position and \(v_i\) its speed. After \(T\) minutes, its position is \(x_i + v_i \times T\). In a lane, if cow \(i\) comes before cow \(j\) (according to increasing starting positions), then they can share the lane only if their final positions satisfy

[ x_i + v_i \times T < x_j + v_j \times T ]

Determine the minimum number of lanes required so that no cow ever encounters another in the same lane.

inputFormat

The first line contains two integers \(N\) and \(T\): the number of cows and the duration in minutes.

Each of the following \(N\) lines contains two integers: the starting position and the speed of a cow.

outputFormat

Output a single integer representing the minimum number of lanes required.

sample

3 5
1 2
3 1
6 3

2