시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 2048 MB93350.000%

문제

Busy Beaver is an avid fan of Sheet Music Boss and dreams of playing long, intricate pieces on his piano. However, with only a measly $10$ fingers, there's not much he can do. Fortunately, his friend Ditto can grow an arbitrary number of fingers on their hand, letting them play any piece imaginable.

Ditto is trying to play a song consisting of $N$ notes, numbered $1$ to $N$. To play the $i$-th note, Ditto must press key $k_i$ at time $a_i$ and let go at time $b_i$. It is guaranteed that no two notes with the same key are played at the same time. In other words, for all pairs of notes $(i,j)$ where $k_i=k_j$, either $b_i\le a_j$ or $b_j\le a_i$.

Ditto plans to use a single hand with $F$ fingers, numbered left to right from $1$ to $F$, to play the song. They want to assign the finger $f_i$ to the $i$-th note. Ditto can play the song if they can assign a finger to each note to satisfy the following criteria:

  • At no point in time do their fingers cross. Formally, for all pairs of notes $(i,j)$ where there exists a time $t$ where $a_i < t < b_i$ and $a_j < t < b_j$, if $k_i < k_j$, then $f_i < f_j$.

Ditto is allowed to delete up to $M$ notes from the song, where $M$ is $\mathbf{0}$ or $\mathbf{1}$. Find the minimum number of fingers they need on their hand in order to play the rest of the song. In other words, find the smallest $F$ where there exists a finger assignment $f$ that satisfies the above criteria.

입력

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1\le T\le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $N$ and $M$ ($1\le N\le 2\cdot 10^5$, $M=0$ or $1$).

The $i$-th of the next $N$ lines contains three integers $k_i$, $a_i$, and $b_i$ ($1\le k_i \le 10^9$, $1\le a_i < b_i \le 10^9$) --- meaning that the $i$-th note uses key $k_i$ from time $a_i$ to time $b_i$.

It is guaranteed that no two notes with the same key are played at the same time and the sum of $N$ over all test cases does not exceed $2\cdot 10^5$.

출력

For each test case, print the minimum number of fingers Ditto needs on their hand so that after at most $M$ note deletions, there exists a satisfactory finger assignment.

서브태스크

번호배점제한
110

The sum of $N$ over all test cases does not exceed $10^3$ and $M=0$.

220

$M=0$.

370

No additional constraints.

예제 입력 1

5
5 0
3 3 6
5 2 5
6 5 6
1 1 4
1 5 7
5 1
2 1 6
10 1 6
4 5 9
8 5 9
6 8 10
4 1
1 1 2
2 1 2
1 3 4
2 3 4
1 0
6 2 5
1 1
6 2 5

예제 출력 1

3
3
2
1
0

노트

The notes for the first test case are shown below. The x-axis is the key pressed, and the y-axis is the time interval the note is pressed. The minimum number of fingers required is $3$ --- each note is labeled with a finger to achieve this.

The notes for the second test case are shown below. Deleting either the yellow or blue note would make $3$ fingers sufficient, and this is optimal.

채점 및 기타 정보

  • 예제는 채점하지 않는다.