끊기지 않는 안내 구간

문제

한 버스 노선의 운행 경로를 출발점 0부터 종점 L까지의 직선으로 나타낸다. 경로 위의 위치는 거리로 구분하며, 정류장이 없는 위치도 경로에 포함된다. 노선 운영자는 경로 전체에 임시 안내 방송을 제공하려 한다. 안내 장치 하나를 설치하면 해당 장치가 담당하는 구간 안에서 방송을 들을 수 있다. 설치 후보는 N개다. i번째 후보의 담당 구간은 왼쪽 끝점 a_i와 오른쪽 끝점 b_i로 주어진다. 이 후보를 선택하면 a_i 이상 b_i 이하인 모든 위치가 안내된다. 구간의 양 끝점도 안내 범위에 포함된다. 후보마다 장치 하나만 설치할 수 있으며, 설치 비용은 모두 같다. 담당 구간을 늘리거나 줄이거나 다른 위치로 옮길 수는 없다. 서로 다른 후보의 담당 구간이 같을 수도 있다. 운영자는 선택한 장치들의 안내 범위를 합쳤을 때 0부터 L까지의 모든 위치가 포함되기를 원한다. 두 구간이 한 끝점에서 만나는 것은 허용된다. 예를 들어 한 구간이 위치 4에서 끝나고 다른 구간이 위치 4에서 시작하면 그 사이에는 안내가 끊긴 곳이 없다. 그러나 두 구간 사이에 길이가 양수인 빈틈이 있으면 조건을 만족하지 못한다. 정수 위치만 안내되는 것으로는 충분하지 않으며, 정수가 아닌 위치까지 모두 안내되어야 한다. 조건을 만족하도록 설치할 수 있는 장치 수의 최솟값을 구하는 프로그램을 작성한다. 모든 후보를 선택해도 경로 전체를 안내할 수 없다면 -1을 출력한다. 최소 개수를 만드는 후보 조합이 여러 개여도 개수만 출력하므로 조합 사이의 우선순위는 없다.

입력

첫째 줄에 정수 N과 L이 공백으로 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ L ≤ 1,000,000이다.
다음 N개 줄의 i번째 줄에 정수 a_i와 b_i가 공백으로 주어진다. 0 ≤ a_i < b_i ≤ L이다. 후보 구간은 임의의 순서로 주어지며 같은 구간이 여러 번 주어질 수 있다.

출력

경로 전체를 안내하는 데 필요한 장치 수의 최솟값을 정수 하나로 출력한다. 불가능하면 -1을 출력한다.

5 12
0 4
3 8
0 6
6 10
9 12

3

3 9
0 3
4 8
7 9

-1

3 7
0 7
0 7
2 6

1

출처: Devin.KR 자체 제작