메신저 기록 보관 구간

문제

사내 메신저 운영팀은 점검 기간에 작성된 공지 기록을 보관하려 한다. 점검 기간은 1번 시각부터 T번 시각까지이며, 시각은 정수 단위로 구분한다. 운영팀은 이 기간의 모든 정수 시각에 대해 기록이 보관되도록 해야 한다. 보관 서버에는 사용할 수 있는 보관 작업이 N개 등록되어 있다. i번 작업을 선택하면 L_i번 시각부터 R_i번 시각까지의 기록을 한꺼번에 보관한다. 양 끝 시각도 포함한다. 각 작업은 전체를 선택하거나 선택하지 않을 수 있으며, 작업의 보관 구간을 줄이거나 늘릴 수는 없다. 하나의 작업을 여러 번 선택할 필요는 없다. 선택한 작업들의 보관 구간은 서로 겹쳐도 된다. 같은 시각의 기록이 여러 작업에 포함되어도 추가 이익이나 불이익은 없다. 또한 시각은 정수이므로, 어떤 작업이 6번 시각까지 보관하고 다른 작업이 7번 시각부터 보관한다면 두 작업 사이에는 보관되지 않은 시각이 없다. 반면 8번 시각부터 시작하는 작업만 이어진다면 7번 시각은 별도로 보관해야 한다. 각 작업을 실행하는 데 드는 운영 비용은 모두 같다. 따라서 운영팀은 전체 점검 기간을 빠짐없이 보관하면서 선택하는 작업의 수를 최소화하려 한다. 입력에 등장한 순서는 작업의 실행 순서와 관계없으며, 선택한 작업들은 어떤 순서로 실행해도 된다. 전체 기간을 보관하는 것이 불가능할 수도 있다. 필요한 작업 수의 최솟값을 구한다. 최적의 선택이 여러 개여도 작업 번호는 출력하지 않는다.

입력

첫째 줄에 정수 N과 T가 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ T ≤ 100,000,000이다.
다음 N개 줄의 i번째 줄에 정수 L_i와 R_i가 주어진다. 1 ≤ L_i ≤ R_i ≤ T이다. 같은 구간을 가진 작업이 여러 개 주어질 수 있다.

출력

1번 시각부터 T번 시각까지 모든 정수 시각을 보관하는 데 필요한 작업 수의 최솟값을 출력한다. 불가능하면 -1을 출력한다.

5 12
1 4
3 8
5 10
9 12
1 2

3

3 9
1 3
5 7
7 9

-1

3 1
1 1
1 1
1 1

1

출처: Devin.KR 자체 제작