서두르는 플로터

플로터는 컴퓨터에 연결해 그림을 출력하는 벡터 그래픽 출력 장치다. 플로터에는 펜 플로터와 정전식 플로터 두 종류가 있다. 펜 플로터는 종이 위에서 펜을 움직여 출력한다. 글자를 포함한 복잡한 선 그림도 그릴 수 있지만, 펜이 기계적으로 움직이는 탓에 속도가 아주 느리다. 이 문제는 그 느린 속도를 다룬다.

이산 수평 펜 플로터는 두 끝점의 좌표가 모두 정수인 수평 선분만 그린다. 그리는 방식은 단순하다. 펜은 종이의 왼쪽 위 모서리($x = y = 0$)에서 출발해 오른쪽으로만 움직이며 그 행에서 그리기로 한 선분을 그린다. 그런 다음 왼쪽 끝까지 완전히 되돌아온 뒤 한 행 아래로 내려가($y \leftarrow y + 1$) 다음 행에서 같은 일을 반복한다. 즉 펜은 왼쪽 끝($x = 0$)에 있을 때만 아래로 내려갈 수 있고, 한 행에서 왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번까지만 지나갈 수 있다.

펜을 왼쪽으로 한 칸($x \leftarrow x - 1$) 또는 오른쪽으로 한 칸($x \leftarrow x + 1$) 옮기는 데 시간 1이 든다. 펜이 종이에 닿아 선분을 그리는 중이라면 이 시간은 두 배가 된다. $x = 0$에서 한 행 아래로 내려가는 데는 시간이 들지 않는다. 플로터는 마지막 선분을 다 그린 순간 멈추므로, 마지막으로 그린 행에서는 $x = 0$까지 되돌아오는 시간을 쓰지 않는다.

선분을 모두 그리려면 시간이 오래 걸릴 수 있어 플로터에 그리기 제한 시간을 새로 넣었다. 플로터는 위의 방식을 그대로 지키면서 제한 시간 안에 그리는 선분의 개수를 최대로 만들어야 한다. 제한 시간과 선분이 주어질 때 이 최댓값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 정수 $n$과 $t$가 주어진다. $n$은 선분의 개수($n \le 1000$)이고, $t$는 제한 시간($t \le 10^6$)이다. 이어지는 $n$개의 줄에는 선분 하나를 나타내는 정수 $y$, $x_s$, $x_t$가 주어진다. $y$는 그 선분이 놓인 행이고($0 \le y \le 2000$), $x_s$와 $x_t$는 두 끝점의 $x$좌표다($0 \le x_s \le x_t \le 10^6$). 선분끼리는 서로 떨어져 있고 교차하지 않는다. $n$과 $t$가 모두 0인 줄은 입력의 끝을 뜻하며 테스트 케이스가 아니다.

$i$번째 테스트 케이스의 답을 출력의 $i$번째 줄에 쓴다. 각 줄에는 그 테스트 케이스의 제한 시간 안에 그릴 수 있는 선분의 최대 개수를 정수 하나로 출력한다.