고무줄 늘이기

Mary는 고무줄을 가지고 노는 것을 좋아한다. 오늘은 Mary의 생일이며, 당신은 선물을 사기 위해 고무줄 가게에 갔다.

가게에는 N개의 고무줄이 있다. 이 고무줄 중 i번째 고무줄은 양 끝을 포함하여 [$A_{i}$, $B_{i}$] 범위 안의 어떤 길이로든 늘어날 수 있다. 범위가 [a, b]인 고무줄과 범위가 [c, d]인 고무줄을 연결하면 [a+c, b+d] 범위 안의 어떤 길이로든 늘어날 수 있는 하나의 고무줄을 만들 수 있다. 이렇게 새로 만든 고무줄도 다른 고무줄과 연결할 수 있으며, 이 과정을 계속할 수 있다.

Mary에게 정확히 L의 길이로 늘어날 수 있는 고무줄을 주고 싶다. 이는 고무줄 하나일 수도 있고 여러 고무줄을 조합한 것일 수도 있다. 사용할 수 있는 돈은 M달러이다. 지출할 수 있는 최소 금액은 얼마인가? 목표를 달성할 수 없다면 대신 IMPOSSIBLE을 출력한다.

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 1 ≤ $P_{i}$ ≤ M. 1 ≤ L ≤ 10000. 1 ≤ $A_{i}$ ≤ $B_{i}$ ≤ 10000.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 1 ≤ M ≤ 100.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000. 1 ≤ M ≤ 1000000000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 가게에 있는 고무줄의 수, 가지고 있는 달러의 액수, 원하는 고무줄의 길이를 나타내는 3개의 정수 N, M, L로 시작한다. 그다음 N개의 줄이 주어진다. 각 줄은 고무줄 하나를 나타내며 3개의 정수 $A_{i}$, $B_{i}$, $P_{i}$로 구성된다. [$A_{i}$, $B_{i}$]는 i번째 고무줄이 늘어날 수 있는 길이의 양 끝을 포함하는 범위이고, $P_{i}$는 i번째 고무줄의 가격을 달러로 나타낸 값이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), 위에서 설명한 목표를 만족하도록 고무줄을 살 수 없다면 y는 IMPOSSIBLE이고, 그렇지 않다면 지불할 수 있는 최소 가격을 나타내는 정수이다.

예제 케이스 #1에서는 가게의 어떤 고무줄도 그 자체로는 충분히 길지 않다. 가장 저렴한 고무줄 두 개를 사서 연결하는 방법은 효과가 없다. 새 고무줄의 늘어날 수 있는 범위가 $[7, 9]$이며, 이 범위에는 6이 포함되지 않기 때문이다. (고무줄은 정확히 L의 길이로 늘어날 수 있어야 한다는 점을 기억하라.) 최적해는 가격이 각각 2와 5인 고무줄을 사서 연결하는 것이다. 새 고무줄의 늘어날 수 있는 범위는 $[4, 7]$이며, 이 범위에는 6이 포함된다. 가지고 있는 돈은 8달러이므로 총비용 7달러를 감당할 수 있다.

예제 케이스 #2에서는 길이 14까지 늘어날 수 있게 하려면 모든 고무줄을 사야 한다. 그러려면 12달러가 들지만, 가진 돈은 11뿐이므로 이 케이스의 답은 IMPOSSIBLE이다.