1701 - Rods
Time Limit : 1 Second
Memory Limit : 256 MB
Submission: 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