34906번 - Ditto Piano 서브태스크다국어

문제

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.

제한

서브태스크

노트

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.