1701 - Rods

Time Limit: 1s Memory Limit: 256MB

Submissions: 7 Solved: 3
Description

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. 

Input

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.

Limits

  • 1 ≤ N ≤ 240.
  • 1 ≤ L ≤ 320.
  • 1 ≤ Ai ≤ Bi ≤ 320 for every i between 1 and N.
  • 1 ≤ Wi ≤ 109 for every i between 1 and N.
  • 1 ≤ T × (N + L) ≤ 16000.

 

Output

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.

Sample Input
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
Sample Output
Case #1: 1998
Case #2: -1
Case #3: 100000
Hint
Source
Lalatina