题目描述

Mary likes playing with rubber bands. It's her birthday today, and you have gone to the rubber band shop to buy her a gift.

There are $N$ rubber bands available in the shop. The i-th of these bands can be stretched to have any length in the range $[A_i, B_i]$, inclusive. Two rubber bands of range $[a, b]$ and $[c, d]$ can be connected to form one rubber band that can have any length in the range $[a+c, b+d]$. These new rubber bands can themselves be connected to other rubber bands, and so on.

You want to give Mary a rubber band that can be stretched to a length of exactly $L$. This can be either a single rubber band or a combination of rubber bands. You have $M$ dollars available. What is the smallest amount you can spend? If it is impossible to accomplish your goal, output IMPOSSIBLE instead.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with 3 integers $N$, $M$, $L$, the number of rubber bands available in the shop, the number of dollars you have and the desired rubber band length. Then $N$ lines follow. Each line represents one rubber band and consists of 3 integers, $A_i$, $B_i$, and $P_i$. $[A_i, B_i]$ is the inclusive range of lengths that the i-th rubber band can stretch to, and $P_i$ is the price of the i-th rubber band in dollars.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is IMPOSSIBLE if you cannot buy rubber bands to satisfy the goal described above, or otherwise an integer: the minimum price you can pay.

2
3 8 6
3 5 2
4 4 3
1 2 5
3 11 14
1 3 4
5 5 3
2 6 5

Case #1: 7
Case #2: IMPOSSIBLE

提示

In sample case #1, none of the rubber bands in the shop are long enough on their own. It will not work to buy the two cheapest rubber bands and stick them together, because the new band would have a stretch range of $[7, 9]$, which does not include $6$. (Remember, the rubber band must be able to stretch to a length of exactly $L$.) The optimal solution is to buy the rubber bands costing $2$ and $5$ and stick them together; the new band has a stretch range of $[4, 7]$, which does include $6$. You have $8$ dollars, so you can afford the total cost of $7$ dollars.

In sample case #2, you need to buy all of the rubber bands to be able to stretch to length $14$. That would cost $12$ dollars, but you only have $11$, so this case is IMPOSSIBLE.

Limits

$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$.

Small dataset (Test set 1 - Visible)

$1 \le N \le 10$.

$1 \le M \le 100$.

Large dataset (Test set 2 - Hidden)

$1 \le N \le 1000$.

$1 \le M \le 1000000000$.