Meeting Room Assignment

Time limit2sMemory limit1024 MB

Summary

Pick the most meetings from N time intervals so that K rooms never overlap, where a room needs a gap of at least one time unit between meetings.

Level: Medium6 of 10
Topics: Intervals, Dynamic programming, Sorting
Solved: No attempts yet

Problem

The Seoul City University Information Technology Building has $K$ meeting rooms, and $N$ meetings want to use them.

The room rules are as follows.

Two or more meetings cannot run in the same room at the same time.
A room needs time to be cleaned, so another meeting cannot start in the same room right when a meeting ends.

In other words, take two meetings $A$ and $B$ . Let $A_s$ and $B_s$ be their start times, and let $A_e$ and $B_e$ be their end times. The two meetings can share a room only if $A_e < B_s$ or $B_e < A_s$ .

Given the start time $(i_s)$ and end time $(i_e)$ of each of the $N$ meetings, find the maximum number of meetings that can use the rooms.

Input

The first line contains the number of meetings $N$ and the number of rooms $K$ . $(1 ≤ N ≤ 200000; 1 ≤ K ≤ 3)$

From the second line through line $N+1$ , each line contains the start time $s_i$ and end time $e_i$ of a meeting, separated by a space. These are positive integers. $(1 ≤ i_s, i_e ≤ 10^9)$

Output

Print the maximum number of meetings that can be held in the rooms.

Examples1

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