스마트 콘센트 배정

문제

스마트 홈의 에너지 관리 허브에는 전기 콘센트가 K개 있고, 시각은 한 시간 단위로 1, 2, 3, … 처럼 정수로 매겨진다. 가전기기 N대가 각각 정확히 한 시간짜리 작동을 요청한다. i번째 기기는 시각 a_i 이상 b_i 이하의 정수 시각 중 하나를 골라야 하고, 고른 시각 한 시간 동안 콘센트 하나를 사용한다. 같은 시각에 동시에 작동할 수 있는 기기는 최대 K대이며, 한 기기는 하루에 한 번만 작동할 수 있다. 허용 구간 안에서 시각을 배정받지 못한 기기는 작동하지 않고 요청이 버려진다. 허브가 작동시킬 수 있는 기기 수의 최댓값을 구하는 프로그램을 작성하라. 시각은 최대 10^9 까지 커질 수 있으므로 비어 있는 시각을 하나씩 훑는 방식은 시간 안에 끝나지 않는다. 같은 구간을 가진 기기가 여러 대여도 각각 별개의 기기로 센다.

입력

첫 줄에 기기 수 N 과 콘센트 수 K 가 공백으로 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 200,000) 이어지는 N개의 줄에 각 기기의 a_i 와 b_i 가 공백으로 주어진다. (1 ≤ a_i ≤ b_i ≤ 10^9, 모두 정수)

출력

작동시킬 수 있는 기기 수의 최댓값을 한 줄에 출력한다.

5 1
1 1
1 2
1 2
2 3
5 5

4

4 2
3 3
3 3
3 3
4 4

3

출처: Devin.KR 자체 제작