UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2474. 订单

统计 下载数据

Description

A经常会收到很多的定单。定单的内容为在第a天到第b**团队将要在A的公司狂欢(包括第a天与第b天)。一旦接受了某一个定单,A公司就必须在第a天到第b天为该团队提供娱乐服务,中途不能取消服务。要如何安排才能使得接受的定单最多呢?
现在告诉你A公司最多能同时服务的的团队数目以及收到的所有定单,求出可以接受的定单的最大值。

Input

文件的第一行包含一个整数T,表示数据组数。
对于每组数据,第一行包含两个整数nm,分别表示收到的定单数和公司能同时服务的团队数。接下来n行每行包含两个整数ab,表示一个定单的内容:某个团队将在第a天与第b天之间在A公司进行狂欢。

Output

对于每组数据输出一行。该行仅包含一个整数,表示最多能接受的定单数。

Sample Input

2
2 1
1 2
2 3
2 1
1 2
3 4

Sample Output

1
2
[

Hint

对于100%的数据 T<=50,m<=40000,n<=100000,∑n<=200000

 

Source