Bài toán: Tối đa hóa số phim có thể xem tại lễ hội phim

Đề bài

Cho một lễ hội phim với ~ n ~ bộ phim được chiếu và ~ k ~ thành viên của câu lạc bộ phim. Mỗi thành viên có thể xem tối đa một bộ phim tại một thời điểm. Bạn biết thời gian bắt đầu và kết thúc của từng bộ phim.

Nhiệm vụ của bạn là xác định số lượng phim tối đa mà các thành viên câu lạc bộ có thể xem hoàn toàn nếu họ hành động một cách tối ưu.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ k ~: số bộ phim và số thành viên câu lạc bộ.
• Sau đó có ~ n ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: thời gian bắt đầu và thời gian kết thúc của một bộ phim.

Output

• In ra một số nguyên: số lượng phim tối đa mà các thành viên câu lạc bộ có thể xem hoàn toàn.

Ràng buộc

• ~ 1 \leq k \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq a < b \leq 10^9 ~

Ví dụ

Input:

5 2
1 5
8 10
3 6
2 5
6 9

Output:

4

Giải thích:

• Các phim được chọn là:
  • Thành viên 1: ~ [1, 5], [6, 9] ~
  • Thành viên 2: ~ [3, 6], [8, 10] ~