31806번 - 구조대

문제

준긋이는 학교 구조대 대장이다. 이번에 고양이들이 지하에 갇혀있다는 소식을 듣고 구조를 하러 가기로 했다. 하지만 구조대의 구성원들이 학생이라 담당 선생님께 허락을 받은 $M$시간 동안만 활동할 수 있다. 단, 한 번 활동을 시작하면 $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$
• 모든 입력은 정수이다.

힌트