题目描述

绘图仪是一种连接计算机以打印图形绘图的矢量图形打印设备。绘图仪有两种类型：笔式绘图仪和静电绘图仪。笔式绘图仪通过移动笔在纸张表面进行打印。它们可以绘制复杂的线条艺术，包括文本，但由于笔的机械运动，绘制速度非常慢。在这个问题中，我们考虑这种特殊类型的笔式绘图仪的慢速问题。离散水平笔式绘图仪只能绘制端点具有离散坐标（整数$x$和$y$）的水平线段。绘制方法非常简单。笔从纸张的左上角（$x=y=0$）开始，仅在该行向右移动时绘制指定的线条。然后，它完全返回到左侧，向下移动一行（$y \leftarrow y+1$），并对第二行重复此任务。对后续行也是如此。换句话说，笔只有在最左侧（即$x=0$）时才能向下移动，并且每行最多只能有一次从左到右的移动和一次从右到左的移动。

将笔向左（$x \leftarrow x-1$）或向右（$x \leftarrow x+1$）移动一个单位长度需要一个单位时间。如果笔在纸上并正在绘制线段，则此时间加倍。向下移动一行（当$x=0$时）不需要时间。

由于绘图仪绘制所有给定线段可能需要很长时间，我们决定为绘图仪添加一个新功能：绘制时间限制。通过指定时间限制，绘图仪应在该时间限制内绘制尽可能多的线段（使用上述相同的绘制方法）。给定时间限制和线段，您应该找到这个最大数量。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个整数$n$和$t$。整数$n$是线段的数量（$n \leq 1000$），$t$是时间限制（$t \leq 10^6$）。接下来的$n$行每行用三个整数$y$、$xs$和$xt$指定一个线段。整数$y$表示该线段所在的行（$0 \leq y \leq 2000$），$xs$和$xt$是其端点的$x$坐标（$0 \leq xs \leq xt \leq 10^6$）。这些线段互不相交且没有重叠。当$n = t = 0$时，表示输入结束，不应处理。

输出格式

将第$i$个测试用例的结果输出到第$i$行。每行应仅包含一个整数，表示对应测试用例中可以绘制的最大线段数量。

样例输入

1 3
0 1 2
3 5
1 1 2
3 1 3
1 3 4
3 6
1 1 2
3 1 3
1 3 4
4 11
1 3 4
1 1 2
2 1 2
2 3 4
0 0

样例输出

1
1
2
3

来源

2009年德黑兰