Teodor는 거짓말쟁이가 아니다!

Young Teodor는 그림 그리기를 즐긴다. 그가 가장 좋아하는 취미는 자신의 거대한 [1;m] 선분 안에 끝점의 좌표가 정수인 선분들을 그리는 것이다. 어느 날 Teodor는 자신이 방금 그린 그림에 흥미로운 특징이 하나 있다는 것을 알아차렸다. 그림의 각 선분에 모두 속하는 정수 좌표의 점이 존재하지 않는다는 것이다. 이 사실을 발견한 Teodor는 이를 Sasha에게 알려 주기로 했다.

Sasha는 Teodor가 자랑하기를 좋아한다는 것을 알기 때문에 그를 전혀 믿지 않는다. Teodor는 자신도 때로는 믿을 만하다는 것을 증명하고 싶어서, 자신의 그림에는 각 선분에 모두 속하는 정수 좌표의 점이 없다는 사실을 Sasha에게 납득시키기로 했다. However Teodor는 게으른 사람이라 Sasha에게 선분들의 모든 끝점 좌표도, 선분의 개수도 알려 주고 싶지 않았다. 그래서 Sasha가 자신에게 '정수 좌표의 점 xi이 주어질 때, Fedya의 그림에서 그 점을 포함하는 선분은 몇 개인가?'라는 일련의 질문을 하도록 제안하고, 이 질문들에 정확히 답하겠다고 약속했다.

두 소년은 모두 공부하느라 매우 바쁘고 시간이 많지 않다. 따라서 Sasha가 Teodor에게 몇 개의 질문을 할 수 있으면서, 그 질문들에 대한 답만으로는 Teodor가 자신에게 거짓말하지 않았다고 확신할 수 없는지 구해 달라고 한다. Sasha는 Teodor의 그림에 있는 선분의 개수를 모른다는 점에 유의한다. 물론 Sasha는 똑똑하므로 같은 점에 관해 두 번 질문하지 않는다.

입력의 첫 번째 줄에는 두 정수 n와 m (1 ≤ n, m ≤ 100 000)가 주어진다. 이는 Teodor의 그림에 있는 선분의 개수와 Sasha가 질문할 수 있는 점의 좌표의 최댓값이다.

이어지는 n개 줄 중 i번째 줄에는 두 정수 li와 ri (1 ≤ li ≤ ri ≤ m)가 주어진다. 이는 그림에 있는 i번째 선분의 왼쪽 끝점과 오른쪽 끝점이다. 선분의 왼쪽 끝점과 오른쪽 끝점이 같은 점일 수도 있음에 유의한다.

모든 선분에 속하는 정수 좌표의 점이 존재하지 않음이 보장된다.

출력의 한 줄에 정수 k 하나를 출력해야 한다. k는 모든 xi가 서로 다르고, 1 ≤ xi ≤ m이며, cnt(xi)가 좌표 xi인 점을 포함하는 선분의 개수일 때, 이 집합만 알고 (n는 모르는) 사람은 초기 그림의 모든 선분에 속하는 점이 존재하지 않는다고 확신할 수 없게 하는 집합 (xi, cnt(xi))의 최대 크기이다.

첫 번째 예제는 Sasha가 Teodor가 자신에게 거짓말하지 않았다고 절대로 확신할 수 없는 상황을 보여 준다. 선분 [1;4]의 각 점에 대한 cnt(xi)를 알더라도, 이 경우와 Teodor가 전체 [1;4] 선분을 그린 경우를 구별할 수 없기 때문이다.

두 번째 예제에서 Sasha는 예를 들어 1, 2, 3, 5, 6의 5개 점에 관해 질문하고도 Teodor가 자신에게 거짓말하지 않았는지 여전히 확신할 수 없다. 하지만 [1;6] 선분의 모든 점에 관한 정보를 알게 되는 순간, Sasha는 Teodor가 자신에게 거짓말하지 않았다고 확신할 수 있다.