竞赛基础算法

【题目描述】穿越时空（Siworae）POJ 1230

琳琳要使用魔法力穿越时空，如图6.7所示，在时空中有一些时空乱流（灰色区域）。时空乱流平行于X轴，宽度为一个单位，但长度各不相同，并且同一区域上不会有两个时空乱流。现在她要从上方沿Y轴方向，走到下方。途中可以穿越部分时空乱流，但会消耗一部分魔法力，所以穿越数不能超过一个值k。要保证琳琳无论从X轴哪点出发，都能走到下方，就必须湮灭某些时空乱流，使得每条路上的时空乱流数都不超过穿越的限定值。现给定时空乱流的分布与穿越限定值，问至少湮灭多少时空乱流，可保证每条路上的时空乱流数不超过该限定值。例如图7.6中，当穿越限定值k＝3时，琳琳除了X轴为6的点外，可以从X轴的任何一点出发。

图6.7

 

【输入格式】

输入有多组测试数据，第一行为组数t（1≤t≤10），随后是每组测试数据，第一行为两个整数n（1≤n≤100），表示时空乱流数，和穿越限定值k（0≤k≤100），以下n行表示时空乱流的起始坐标和结束坐标。

【输出格式】

每组一行数据，表示最少湮灭的时空乱流数。

【输入样例】

2

3 1

2 0 4 0

0 1 1 1

1 2 2 2

7 3　　（此例即为图7.6中所示）

0 0 3 0

6 1 8 1

2 3 6 3

4 4 6 4

0 5 1 5

5 6 7 6

1 7 3 7

【输出样例】

1

1