Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

DVD Rental Store

By zobayer · Limits 1s, 512 MB

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 , Vi100, 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

InputOutput
1
3 1
1 4 8
2 3 5
3 5 4
9

    Discussion

    Statistics


    100% Solution Ratio

    Deshi_TouristEarliest, 3w ago

    Deshi_TouristFastest, 0.0s

    Deshi_TouristLightest, 262 kB

    Deshi_TouristShortest, 3998B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.