고무줄 늘이기 (라지)

메리는 고무줄을 가지고 노는 것을 좋아한다. 오늘이 메리의 생일이라 선물을 사러 고무줄 가게에 왔다.

가게에는 고무줄이 $N$개 있다. $i$번 고무줄은 $A_i$ 이상 $B_i$ 이하인 아무 길이로나 늘일 수 있다. 늘일 수 있는 길이 범위가 $[a, b]$인 고무줄과 $[c, d]$인 고무줄을 이으면, 길이 범위가 $[a+c, b+d]$인 고무줄 하나가 된다. 이렇게 만든 고무줄도 다른 고무줄과 다시 이을 수 있다.

메리에게 길이를 정확히 $L$로 늘일 수 있는 고무줄을 선물하려고 한다. 고무줄 한 개여도 되고 여러 개를 이어 붙인 것이어도 된다. 쓸 수 있는 돈은 $M$달러다. 최소 얼마를 쓰면 되는가? 목표를 이룰 방법이 없으면 IMPOSSIBLE을 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $N$, $M$, $L$이 주어진다. 차례대로 가게에 있는 고무줄의 개수, 쓸 수 있는 돈, 원하는 고무줄 길이다. 이어서 $N$개의 줄에 고무줄 하나씩의 정보가 주어진다. 각 줄에는 정수 $A_i$, $B_i$, $P_i$가 주어진다. $[A_i, B_i]$는 $i$번 고무줄을 늘일 수 있는 길이 범위이고, $P_i$는 $i$번 고무줄의 가격이며 단위는 달러다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 조건을 만족하도록 고무줄을 살 수 없으면 $y$는 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 \le N \le 1000$
• $1 \le M \le 1000000000$

첫 번째 예제의 1번 테스트 케이스에서는 고무줄 하나만으로는 길이 6에 닿지 못한다. 가장 싼 고무줄 두 개를 이으면 범위가 $[7, 9]$가 되어 6을 포함하지 않으므로 이 조합도 답이 아니다. 고무줄은 길이를 정확히 $L$로 늘일 수 있어야 한다. 가격이 2인 고무줄과 5인 고무줄을 사서 이으면 범위가 $[4, 7]$이 되어 6을 포함한다. 쓸 수 있는 돈이 8달러이므로 합계 7달러를 낼 수 있다.

2번 테스트 케이스에서는 길이 14를 만들려면 고무줄을 모두 사야 한다. 그러면 12달러가 드는데 쓸 수 있는 돈은 11달러뿐이라 IMPOSSIBLE이다.