Car Fleet

Cars drive on a one-lane road towards a target at mile target. Each car is a pair [position, speed]: it starts at position (all different, all below target) and drives at a constant speed. A car cannot overtake: when a faster car catches up to a slower one it slows down and drives right behind it, and they continue as a fleet (at the speed of the slowest). A single car is a fleet too.

Return the number of fleets that arrive at the target.

For target = 12 and cars = [[10, 2], [8, 4], [0, 1], [5, 1], [3, 3]] the answer is 3.

Examples

Example 1

Input:

car_fleet(12, [[10, 2], [8, 4], [0, 1], [5, 1], [3, 3]])

Output:

3

Example 2

Input:

car_fleet(10, [[3, 3]])

Output:

1

Constraints

• 0 <= number of cars <= 200000
• 0 <= position < target <= 10**9, all positions different
• 1 <= speed <= 10**6