관광

여행할 때는 가능한 한 많은 도시에서 관광하며 시간을 보내고 싶지만, 다음 도시로 가는 버스를 타야 하므로 때로는 그러지 못할 수도 있다. 여행의 즐거움을 극대화하기 위해 일정을 최적화하는 프로그램을 작성하기로 한다.

시간 0에 도시 1에서 출발하여, 모든 도시를 방문하면서 도시 2부터 N까지 오름차순으로 여행할 계획이다. 모든 도시 i에서 다음 도시 i + 1로 가는 버스 노선이 있다. i번째 버스 노선은 출발 시각, 운행 간격, 이동 시간을 나타내는 3개의 정수 $S_{i}$, $F_{i}$, $D_{i}$로 지정된 일정에 따라 운행한다. 형식적으로 이는 x가 정수이고 x ≥ 0일 때, 모든 시각 $S_{i}$ + $xF_{i}$에 도시 i에서 출발하는 버스가 있으며, 그 버스가 도시 i + 1에 도착하는 데 $D_{i}$의 시간이 걸린다는 뜻이다.

1부터 N - 1까지의 각 도시에서 다음 버스를 기다리기 전에 $T_{s}$의 시간 동안 관광할지, 아니면 즉시 다음 버스를 기다릴지 결정할 수 있다. 같은 도시에서 여러 번 관광할 수는 없다. 버스에 타고 내리는 데에는 시간이 걸리지 않는다고 가정해도 된다. 늦어도 시간 $T_{f}$까지 도시 N에 도착해야 한다. (일찍 도착하더라도 도시 N에서는 관광할 수 없다는 점에 유의한다. 그곳에는 볼 것이 없다!)

관광할 수 있는 도시 수의 최댓값은 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ N ≤ 16. 1 ≤ $S_{i}$ ≤ 5000. 1 ≤ $F_{i}$ ≤ 5000. 1 ≤ $D_{i}$ ≤ 5000. 1 ≤ $T_{s}$ ≤ 5000. 1 ≤ $T_{f}$ ≤ 5000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ N ≤ 2000. 1 ≤ $S_{i}$ ≤ $10^{9}$. 1 ≤ $F_{i}$ ≤ $10^{9}$. 1 ≤ $D_{i}$ ≤ $10^{9}$. 1 ≤ $T_{s}$ ≤ $10^{9}$. 1 ≤ $T_{f}$ ≤ $10^{9}$.

입력은 테스트 케이스의 수인 정수 T 하나를 포함하는 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 도시의 수, 어느 도시에서든 관광하는 데 걸리는 시간, 도시 N에 도착할 수 있는 가장 늦은 시각을 나타내는 3개의 정수 N, $T_{s}$, $T_{f}$을 포함하는 한 줄로 시작한다.

이어서 N - 1개의 줄이 주어진다. i번째 줄에는 도시 i에서 도시 i + 1로 운행하는 버스의 출발 시각, 운행 간격, 이동 시간을 나타내는 3개의 정수 $S_{i}$, $F_{i}$, $D_{i}$이 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 늦어도 시간 $T_{f}$까지 도시 N에 도착할 수 있으면서 관광할 수 있는 도시 수의 최댓값이다. 시간 $T_{f}$까지 도시 N에 도착하는 것이 불가능하면 Case #x: IMPOSSIBLE을 출력한다.

첫 번째 테스트 케이스에서는 도시 1에서 관광한 뒤 시간 3에 출발하는 버스를 타고 시간 4에 도착할 수 있다. 도시 2에서 관광한 뒤 시간 8에 출발하는 버스를 탈 수 있다. 시간 10에 도시 3에 도착하면 즉시 다음 버스에 탑승하여 시간 12에 맞춰 도시 4에 도착한다.