You are the owner of a DVD rental store. There are N customers who want to rent a DVD of ‘The Matrix 4’ movie. For each customer you collected three pieces of information: the day they want the DVD, the day they will return the DVD and how much they will pay for it. If a DVD is returned on Day X, then it is available for rent from the same day X.
Now you want to maximize the money you can earn. As there is a limited number of DVDs, it is possible that some customers may not be able to rent the DVD.
Input
Input starts with an integer, T (T ≤ 25) denoting the number of test cases. Each test case starts with two integers, N and K (1 ≤ N, K ≤ 100) where N is the number of customers and K is the number of available DVDs for the movie. Each of the next N lines contain three integers Ui , Vi and Ci (1 ≤ Ui , Vi ≤ 100, Ui < Vi , 1 ≤ Ci ≤ 100) where Ui is the day customer i want to rent the DVD, Vi is the day he will return it and Ci is the amount of money he will pay for it.
Output
For each case, print the maximum amount of money which can be earned.
Sample
| Input | Output |
|---|---|
1 3 1 1 4 8 2 3 5 3 5 4 | 9 |
