UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1317. 计划安排

统计 下载数据

Description

有N位客户希望工厂为他们加工产品。每位客户都提供了需要加工的产品的类型,产品到达工厂的时间r、最迟完成
加工的时间d和每个产品加工所需的时间t。工厂里的生产车间一共有M台机器。每个产品在每台机器上都可以加工
,但是,一台机器在任何时候最多只能加工一件产品,而一件产品在任何时候也最多只能被一台机器加工。同时,
我们可以在某台机器正在加工时将工作打断,换另一个产品加工。问你能否找到一个方案,使得所有的产品都在规
定的时间内完成加工?

Input

第一行包含一个整数Q,表示数据组数。接下来Q组数据,
每组数据的第一行包含两个整数N,M,表示需要加工的产品的数量、机器的数量。
接下来N行,每行三个整数ti、ri、di,表示加工产品所需的时间,产品到达工厂的时间以及最迟完成加工的时间
即产品可以在[ri,di)内被加工
1<=N<=300,1<=M<=300

Output

包含Q行,每行对应一组数据的答案。
如果第i组数据能搞找到一个方案,则第i行包含一个Yes,否则包含一个No

Sample Input

2
2 1
3 6 10
4 8 12
3 1
2 2 9
2 3 5
3 5 8

Sample Output

No
Yes

Hint

Source