고무줄 늘이기 (Small)

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

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

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

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

각 테스트 케이스의 첫째 줄에는 정수 세 개 $N$, $M$, $L$이 주어진다. $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 N \le 10$
• $1 \le M \le 100$
• $1 \le P_i \le M$
• $1 \le L \le 10000$
• $1 \le A_i \le B_i \le 10000$

예제의 첫 번째 테스트 케이스에서는 고무줄 하나만으로 길이 6을 만들 수 없다. 가격이 가장 싼 고무줄 두 개를 이으면 길이 범위가 $[7, 9]$가 되어 6이 들어가지 않는다. 고무줄은 길이를 정확히 $L$로 늘일 수 있어야 한다. 가격이 2인 고무줄과 5인 고무줄을 이으면 범위가 $[4, 7]$이 되어 6을 만들 수 있고, 이때 드는 7달러는 가진 돈 8달러 안에 들어간다.

두 번째 테스트 케이스에서 길이 14를 만들려면 고무줄 세 개를 모두 사야 하는데, 그 값은 12달러다. 가진 돈은 11달러뿐이므로 IMPOSSIBLE이다.