31781번 - 학교를 무너뜨리는 포닉스

문제

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

포스텍의 건물은 아래와 같은 구조로 이루어져 있다.

• 포스텍의 건물은 직사각형 모양의 벽돌들을 쌓아서 지어졌다. 이때 사용된 벽돌들은 모두 높이가 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 500\ 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 각 벽돌의 정보를 나타내는 3ドル$개의 정수 $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ドル$개의 벽돌을 제거해 무너뜨릴 수 있는 벽돌의 최대 개수를 출력한다.

제한

힌트