题目描述

POJ 1230

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

输入格式

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

输出格式

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

样例

输入样例

2

3 1

2 0 4 0

0 1 1 1

1 2 2 2

7 3　　

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