cho.sh

Stretch Rope (Small)

N is at most 10, so enumerate subsets of bands and find the cheapest subset whose summed intervals contain L and whose total price is within M.

Medium4Brute forceArrayIntervalsDynamic programmingNo attempts yetTime limit5sMemory limit512 MB

Problem

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

The shop has NN rubber bands. The ii-th band can be stretched to any length from AiA_i to BiB_i, both ends included. Connecting a band with range [a,b][a, b] to a band with range [c,d][c, d] makes one band with range [a+c,b+d][a+c, b+d]. A band made that way can be connected to other bands again.

You want to give Mary a band that can be stretched to a length of exactly LL. It can be a single band or a band built by connecting several of them. You have MM dollars. Find the smallest amount you can spend. If the goal cannot be reached, print IMPOSSIBLE.

Input

The first line holds the number of test cases, TT. TT test cases follow.

The first line of each test case holds three integers NN, MM, LL: the number of rubber bands in the shop, the amount of money you have, and the desired length. Each of the next NN lines describes one rubber band with three integers AiA_i, BiB_i, PiP_i. [Ai,Bi][A_i, B_i] is the range of lengths the ii-th band can stretch to, both ends included, and PiP_i is its price in dollars.

Output

For each test case, print one line in the form Case #x: y. Here xx is the test case number, starting from 1. yy is IMPOSSIBLE if you cannot buy rubber bands that meet the goal, and otherwise the minimum price you have to pay.

Limits

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤101 \le N \le 10
  • 1≤M≤1001 \le M \le 100
  • 1≤Pi≤M1 \le P_i \le M
  • 1≤L≤100001 \le L \le 10000
  • 1≤Ai≤Bi≤100001 \le A_i \le B_i \le 10000

Hint

In the first test case of the sample, no single band reaches length 6. Buying the two cheapest bands and connecting them gives the range [7,9][7, 9], which does not contain 6. The band must stretch to a length of exactly LL. Connecting the band that costs 2 with the band that costs 5 gives the range [4,7][4, 7], which does contain 6, and the total of 7 dollars fits within the 8 dollars you have.

In the second test case, reaching length 14 needs all three bands, which cost 12 dollars together. You only have 11 dollars, so the answer is IMPOSSIBLE.