One day, you need something with length L, so you go to a shop. There are N rods selling in the shop. The i^th rod can be adjusted from a length of A_i to B_i (inclusive), which costs W_i. 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 A_i, B_i and W_i, whose meaning have been described above.

Limits

• 1 ≤ N ≤ 240.


• 1 ≤ L ≤ 320.


• 1 ≤ A_i ≤ B_i ≤ 320 for every i between 1 and N.


• 1 ≤ W_i ≤ 10⁹ for every i between 1 and N.


• 1 ≤ T × (N + L) ≤ 16000.

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