학교를 무너뜨리는 포닉스

오늘도 열심히 하늘을 날며 곡예 연습을 하던 포닉스는 문득 포스텍의 건물들이 자신의 비행을 방해한다고 생각했다. 더 자유롭게 날고 싶었던 포닉스는 결국 학교 건물을 무너뜨리기로 결심했다!

포스텍의 건물은 다음과 같은 구조로 이루어져 있다.

• 건물은 직사각형 벽돌을 쌓아 지었다. 사용된 벽돌은 모두 높이가 $1$이며, 너비는 벽돌마다 다를 수 있다. 같은 층의 두 벽돌은 서로 겹칠 수 없다.
• 건물은 총 $H$층이며, 각 층의 높이는 $1$이다. 모든 층에는 적어도 $1$개의 벽돌이 있다.
• 건물의 모든 벽돌은 $1$층에 있거나, 바로 아래층의 어떤 벽돌과 직접 맞닿아 있어야 한다. 꼭짓점만 서로 닿은 경우는 맞닿은 것이 아니다. 이 조건을 만족하지 않는 벽돌은 공중에 떠 있다고 한다.

아래 그림에서 건물 A는 위 조건을 모두 만족하는 적절한 건물이다. 건물 B는 7번 벽돌이 공중에 떠 있으므로 적절한 건물이 아니다.

건물 A

건물 B

하지만 굳건하게 지어진 포스텍의 건물을 한순간에 무너뜨리기는 쉽지 않다. 그래서 포닉스는 건물에서 정확히 $1$개의 벽돌을 제거해 최대한 많은 벽돌을 무너뜨리려고 한다. 건물은 다음 과정을 거쳐 무너진다.

1. 포닉스가 $h$층에 있는 벽돌 $1$개를 골라 제거한다.
2. $h+1$층의 벽돌 중 $h$층에서 맞닿아 있던 벽돌이 모두 제거되어 공중에 뜬 벽돌은 즉시 제거된다. 건물에 공중에 뜬 벽돌이 있어서는 안 되기 때문이다.
3. 같은 방식으로 2번 과정에서 제거된 벽돌 때문에 $h+2$층의 일부 벽돌이 공중에 뜨면, 그 벽돌도 즉시 제거된다.
4. 이 과정이 한 층씩 연쇄적으로 일어나며 건물이 무너진다. 공중에 뜬 벽돌이 더 없거나 꼭대기 층에 도달하면 과정이 끝난다.

포닉스는 실제로 무너뜨리기 전에 몇 개의 벽돌이 무너질지 미리 알고 싶어 한다. 포닉스를 대신해 무너뜨릴 수 있는 벽돌 개수의 최댓값을 구하라. 처음에 제거한 벽돌도 무너진 벽돌에 포함된다.

첫 번째 줄에 벽돌의 개수 $N$과 건물의 높이 $H$가 공백으로 구분되어 주어진다. ($1 \leq N, H \leq 500000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 각 벽돌의 정보가 정수 $h_i$, $l_i$, $r_i$로 공백으로 구분되어 주어진다. 이는 $i$번 벽돌이 $h_i$층에 있으며, 좌표평면에서 왼쪽 끝의 $x$좌표가 $l_i$, 오른쪽 끝의 $x$좌표가 $r_i$라는 뜻이다. ($1 \leq h_i \leq H$; $0 \leq l_i < r_i \leq 10^9$)

모든 층에 적어도 $1$개 이상의 벽돌이 있고, 같은 층의 벽돌끼리 겹치지 않으며, 공중에 뜬 벽돌이 없음이 보장된다.

벽돌을 $1$개 제거해 무너뜨릴 수 있는 벽돌의 최대 개수를 출력한다.