Time Limit: 1s
Memory Limit: 256MB
One day, you need something with length L, so you go to a shop. There are N rods selling in the shop. The ith rod can be adjusted from a length of Ai to Bi (inclusive), which costs Wi. You can buy any combination of those rods and link them up to get a longer one. If you link two rods up, the length of the new one can be adjusted between the sum of their minimum and maximum length respectively. Since you are so poor, you want to minimize the total cost. If it’s possible to reach your goal, you have to figure out the least amount of money you need.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consists of two integers N and L representing the number of rods in the shop and the length you want. Then N lines follow, each line consists of three integers Ai, Bi and Wi, whose meaning have been described above.
For each test case, output one line containing “Case #x: y”, where x is the test case number and y is the least amount money you need or “-1” if it’s impossible.
3 3 5 1 2 1000 2 3 999 4 4 998 2 100 40 50 23 61 99 1 3 100 10 90 12 1 9 13 100 120 100000
Case #1: 1998 Case #2: -1 Case #3: 100000