구조대

준긋이는 학교 구조대 대장이다. 이번에 고양이들이 지하에 갇혀 있다는 소식을 듣고 구조하러 가기로 했다. 하지만 구조대원이 학생이라 담당 선생님께 허락받은 $M$시간 동안만 활동할 수 있다. 한 번 활동을 시작하면 $M$시간을 연속으로 활동해야 하며 중간에 쉴 수 없다. 다만 활동을 언제 시작할지는 준긋이가 마음대로 요청할 수 있다. 시작 시각을 $s$($s$는 음이 아닌 정수)라 하면 준긋이는 $s$시 $30$분부터 $s+M$시 $30$분까지 활동하도록 요청할 수 있다.

학교 구조대는 여러 팀으로 이루어져 있으며, 한 팀의 구조 작업은 다음과 같이 진행된다.

• 팀이 현장에 도착하여 현장을 파악한다.
• 팀이 복귀해 상황을 분석하고 필요한 물품을 챙긴다.
• 다시 현장에 도착해 구조 작업을 완료한다.

각 팀에는 고유 번호 $c$가 있으며, 활동 가능한 시간대가 하나 이상 있다. 시간대는 $[l, r)$ 형식이며, $l$시 $00$분부터 $r-1$시 $59$분까지 활동 가능하다는 뜻이다. 현장 도착과 복귀는 활동 가능 시간 중 언제든 할 수 있지만, 한 번 복귀한 시간대에는 같은 시간대 안에서 다시 현장으로 갈 수 없다. 대장인 준긋이는 최소 두 번 이상 현장에 갈 수 있는 팀만 구조에 참여시키려 하며, 이런 팀을 최대한 많이 참여시키고자 한다. 준긋이를 도와 시간을 잘 정해서 가장 많은 팀이 참여할 수 있게 하자.

첫 번째 줄에 활동 가능한 시간대의 개수 $N$과 주어진 시간 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에는 $c$번 팀의 활동 시간대 중 하나인 $[l, r)$를 나타내는 정수 $l$, $r$과 팀의 번호 $c$가 공백으로 구분되어 주어진다.

같은 팀의 모든 활동 시간대는 서로 겹치지 않는다. 엄밀하게, 같은 팀의 임의의 두 시간대 $[l_i, r_i)$와 $[l_j, r_j)$에 대해 $l_i \neq l_j$이고, $l_i < l_j$라면 $r_i < l_j$이다.

첫 번째 줄에 참여할 수 있는 구조대 팀의 최댓값을 출력한다.

• $1 \le N \le 2 \times 10^5$, $1 \le M \le 10^6$
• $0 \le l < r \le 10^6$, $0 \le c \le 10^9$
• 모든 입력은 정수이다.