题目描述

旅行时，你喜欢在尽可能多的城市观光，但有时你可能无法做到，因为你需要赶巴士去下一个城市。为了最大化旅行的乐趣，你决定编写一个程序来优化你的行程安排。

你在时间 $0$ 从城市 $1$ 出发，计划按升序依次前往城市 $2$ 到 $N$，并访问每个城市。从每个城市 $i$ 到下一个城市 $i+1$ 都有巴士服务。第 $i$ 趟巴士服务的时间表由三个整数 $S_i$、$F_i$ 和 $D_i$ 指定，分别表示首班车时间、发车间隔和乘车耗时。形式化地说，这意味着在时间 $S_i + x F_i$（其中 $x$ 为整数且 $x \ge 0$）都有一班巴士从城市 $i$ 出发，该巴士需要 $D_i$ 时间到达城市 $i+1$。

在 $1$ 到 $N-1$ 之间的每个城市（包含两端），你可以选择花 $T_s$ 时间观光，然后再等待下一班巴士；也可以直接等待下一班巴士而不观光。你不能在同一座城市多次观光。假设上车和下车不耗时。你必须在最晚时间 $T_f$ 之前到达城市 $N$。（注意，即使你提前到达城市 $N$，也不能在那里观光，因为那里没什么可看的！）

你最多可以在多少个城市观光？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含三个整数 $N$、$T_s$ 和 $T_f$，分别表示城市的数量、在任何一座城市观光所需的时间，以及到达城市 $N$ 的最晚时间。

接下来 $N-1$ 行，第 $i$ 行包含三个整数 $S_i$、$F_i$ 和 $D_i$，表示从城市 $i$ 到城市 $i+1$ 的巴士的首班车时间、发车间隔和乘车耗时。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是能够在最晚时间 $T_f$ 之前到达城市 $N$ 的前提下，最多可以观光的城市数量。如果不可能在最晚时间 $T_f$ 之前到达城市 $N$，则输出 Case #x: IMPOSSIBLE。

4
4 3 12
3 2 1
6 2 2
1 3 2
3 2 30
1 2 27
3 2 1
4 1 11
2 1 2
4 1 5
8 2 2
5 10 5000
14 27 31
27 11 44
30 8 20
2000 4000 3

Case #1: 2
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 4

提示

在第一个测试用例中，你可以在城市 $1$ 观光，然后乘坐时间 $3$ 出发的巴士，在时间 $4$ 到达城市 $2$。你可以在城市 $2$ 观光，然后乘坐时间 $8$ 出发的巴士。当你于时间 $10$ 到达城市 $3$ 时，立即乘坐下一班巴士，恰好于时间 $12$ 到达城市 $4$。

限制条件

$1 \le T \le 100$。

小数据集（测试集 $1$ – 可见）

$2 \le N \le 16$。

$1 \le S_i \le 5000$。

$1 \le F_i \le 5000$。

$1 \le D_i \le 5000$。

$1 \le T_s \le 5000$。

$1 \le T_f \le 5000$。

大数据集（测试集 $2$ – 隐藏）

$2 \le N \le 2000$。

$1 \le S_i \le 10^9$。

$1 \le F_i \le 10^9$。

$1 \le D_i \le 10^9$。

$1 \le T_s \le 10^9$。

$1 \le T_f \le 10^9$。

翻译由 DeepSeek V4 Pro 完成