Remember the Treasure Hunt Competitions of 1st year? :D
Oh!
If you are 2k18, don't be confused! You haven’t participated in one yet! :)
Nothing to worry if you didn’t participate in a Treasure Hunt yet! SGIPC (Special Group Interested in Programming Contest) is going to arrange one for you.
A treasure hunt is a game where players try to find hidden objects by following a series of clues. Players need to interpret the clues to find the next clue.The final clue leads to the treasure.
Wait! SGIPC is not that harsh you know! We have made a new set of rules to help you earn the treasure you deserve.
By this time you probably have understood that SGIPC will not arrange a competition without compelling you to solve problems. Instead of solving clues, you have to write codes to solve problems. Sounds easier, right?
Before the start of treasure hunt, we will give you M problem statements to read. As you are an experienced programmer, so after reading the problems you know exactly how much time you will need to solve each of them.
Now problems are placed on a straight road of length N units. You start at position 0 and with an initial score 0. You have to reach at position N within K seconds (inclusive) to earn your deserved treasure else you will earn nothing. You can move along the road with an uniform speed of 1 unit/second at any direction. Information about the treasures is given as distance from starting point Di, time required to solve the problem Ci and points earned by solving the problem Pi. You can solve a problem by spending Ci seconds and earn Pi points or skip it to chose another for a better score. You have to earn maximum point to increase the amount of your treasure.
Input
First line contains number of test cases T.
First line of each test case contain N, M and K length of road, number of problems and maximum time to finish the race.
Each of the next M line contain 3 integers Di, Ci and Pi.
- 1<=T<=10
- 1<=N<=5000
- 1<=M<=500 & M<N
- N<=K<= 10000
- 1<=Di <N
- 1<=Ci<=K
- 1<=Pi<=10000000
Output
For each test case, print a line containing the maximum points.
Sample
| Input | Output |
|---|---|
2 6 1 8 3 2 5 6 1 8 3 3 5 | Case 1: 5 Case 2: 0 |
