Minimum Number of Boats

You are given n passengers, each specified by an arrival time and a direction indicator (either 0 or 1). Direction 0 and direction 1 represent the two banks of a river. Each boat has a fixed capacity c and may only transport passengers from one direction per trip.

When a boat departs, it takes the earliest arriving passengers (in the sorted order of arrival time) from that direction until it is full (i.e. until it has boarded c passengers) or there are no passengers left to board from that direction. The process is repeated independently for passengers from each direction. Your task is to determine the minimum total number of boats required to transport all the passengers.

Note: Although the arrival times are provided, they only serve to indicate the order in which passengers board a boat. For the purpose of computing the number of boats, it is sufficient to compute the number of trips (or batches) required for each direction, which is essentially the ceiling of the number of passengers in that direction divided by c, and then sum these up.

inputFormat

The first line contains two integers n and c (1 ≤ n ≤ 10⁵, 1 ≤ c ≤ 10⁵), where n is the number of passengers and c is the boat capacity.

Each of the next n lines contains two integers t and d (1 ≤ t ≤ 10⁹, d ∈ {0, 1}), where t is the arrival time and d is the direction.

outputFormat

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

## sample

5 2
1 0
2 0
3 0
4 0
5 0

3

</p>