# Practice on Toph

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

# Treasure Hunt

Limits 2s, 512 MB

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

InputOutput
```2
6 1 8
3 2 5
6 1 8
3 3 5```
```Case 1: 5
Case 2: 0```

### Statistics

90% Solution Ratio

likhon5Earliest, Apr '19

imAnikFastest, 0.0s

rohijulislamLightest, 20 MB

kzvd4729Shortest, 678B