P16591 [GKS 2016 #D] Stretch Rope

Mary 喜欢玩橡皮筋。今天是她的生日，你去橡皮筋店为她买礼物。 店里有 $N$ 根橡皮筋。第 $i$ 根橡皮筋可以拉伸到任意长度，范围是 $[A_i, B_i]$（包含端点）。两根范围分别为 $[a, b]$ 和 $[c, d]$ 的橡皮筋可以连接成一根新的橡皮筋，新橡皮筋可以拉伸到任意长度，范围是 $[a + c, b + d]$。这些新橡皮筋本身也可以继续与其他橡皮筋连接，依此类推。 你想送给 Mary 一根能恰好拉伸到长度 $L$ 的橡皮筋。这根橡皮筋可以是单独的一根，也可以是若干根组合而成。你手头有 $M$ 美元。请问你最少需要花费多少钱？如果无法实现目标，则输出 `IMPOSSIBLE`。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$M$、$L$，分别表示店里的橡皮筋数量、你拥有的美元数以及目标橡皮筋长度。随后 $N$ 行，每行描述一根橡皮筋，包含三个整数 $A_i$、$B_i$ 和 $P_i$。其中 $[A_i, B_i]$ 是第 $i$ 根橡皮筋可拉伸到的长度范围（包含端点），$P_i$ 是该橡皮筋的价格（美元）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始）。如果无法购买橡皮筋实现上述目标，则 $y$ 为 `IMPOSSIBLE`；否则 $y$ 为一个整数，表示你所支付的最小价格。

在样例 #1 中，店里没有任何一根橡皮筋单独就足够长。购买最便宜的两根并连接也不可行，因为新橡皮筋的拉伸范围为 $[7, 9]$，不包含 $6$。（注意，橡皮筋必须能恰好拉伸到长度 $L$。）最优方案是购买价格为 $2$ 和 $5$ 的橡皮筋并连接；新橡皮筋的拉伸范围为 $[4, 7]$，确实包含 $6$。你有 $8$ 美元，因此可以支付总价 $7$ 美元。 在样例 #2 中，你需要购买所有橡皮筋才能拉伸到长度 $14$。总花费为 $12$ 美元，但你只有 $11$ 美元，因此本案例为 `IMPOSSIBLE`。 ### 限制条件 $1 \le T \le 100$。 $1 \le P_i \le M$。 $1 \le L \le 10000$。 $1 \le A_i \le B_i \le 10000$。 **小数据集（测试集 1 – 可见）** $1 \le N \le 10$。 $1 \le M \le 100$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 1000$。 $1 \le M \le 10^9$。 翻译由 DeepSeek V4 Pro 完成