Transportation Scheduling

This problem simulates a transportation scheduling system for a shared ride service. There are N passengers waiting for a ride and each ride (trip) has a limited seating capacity of C. Each passenger has a pickup location, \(d_i\), and a drop‐off location, \(a_i\). The aim is to group the passengers into the fewest number of trips possible, while preserving the order in which the passengers made their requests.

In each trip, the ordering rule requires that no passenger is dropped off before any other passenger whose drop‐off location comes earlier. In other words, if several passengers share the same trip, and if one passenger's drop-off happens earlier than that of another, then the passenger with the earlier drop-off must be served first. Also, the total number of passengers in any trip cannot exceed the seat capacity \(C\).

Your task is to compute the minimum number of trips required to transport all passengers under the above constraints.

inputFormat

The input is given via stdin and has the following format:

N C
d1 a1
...
dN aN

Where:

• N (1 ≤ N ≤ 10⁵): the number of passengers.
• C (1 ≤ C ≤ N): the seating capacity of each trip.
• Each of the next N lines contains two integers \(d_i\) and \(a_i\) (1 ≤ \(d_i\) < \(a_i\) ≤ 10⁹): the pickup and drop-off locations of the i-th passenger.

outputFormat

The output should be written to stdout as a single integer representing the minimum number of trips required to transport all the passengers.

4 3
1 5
2 6
3 7
4 8

2