Stretch Rope (Large)

Mary likes playing with rubber bands. Today is her birthday, and you have gone to the rubber band shop to buy her a gift.

The shop has $N$ rubber bands. Band $i$ can be stretched to any length in the inclusive range $[A_i, B_i]$. Two rubber bands with ranges $[a, b]$ and $[c, d]$ can be connected into a single band with range $[a+c, b+d]$. A band made this way can be connected to further bands.

You want to give Mary a rubber band that stretches to a length of exactly $L$. It can be one band or several bands connected together. You have $M$ dollars. What is the smallest amount you can spend? If there is no way to reach the goal, print IMPOSSIBLE instead.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case starts with three integers $N$, $M$, $L$: the number of rubber bands in the shop, the number of dollars you have, and the desired length. Then $N$ lines follow, one per rubber band. Each of those lines contains three integers $A_i$, $B_i$, $P_i$, where $[A_i, B_i]$ is the inclusive range of lengths band $i$ stretches to and $P_i$ is its price in dollars.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1. If you cannot buy rubber bands that satisfy the goal, $y$ is IMPOSSIBLE; otherwise $y$ is the minimum price you pay.

• $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 \le N \le 1000$
• $1 \le M \le 1000000000$

In case 1 of the first example, no single band reaches length 6. Connecting the two cheapest bands does not work either, because the new band has range $[7, 9]$, which does not contain 6. The band must stretch to a length of exactly $L$. Buying the band priced 2 and the band priced 5 and connecting them gives range $[4, 7]$, which does contain 6. You have 8 dollars, so you can afford the total of 7 dollars.

In case 2 of the first example, reaching length 14 requires every band in the shop. That costs 12 dollars and you only have 11, so the answer is IMPOSSIBLE.