# Practice on Toph

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

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

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 **D _{i}**, time required to solve the problem

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 **D _{i}**,

**1**<=**T**<=**10****1**<=**N**<=**5000****1**<=**M**<=**500**&**M**<**N****N**<=**K**<=**10000****1**<=**D**<_{i}**N****1**<=**C**<=_{i}**K****1**<=**P**<=_{i}**10000000**

For each test case, print a line containing the maximum points.

Input | Output |
---|---|

2 6 1 8 3 2 5 6 1 8 3 3 5 | Case 1: 5 Case 2: 0 |

90% Solution Ratio

likhon5Earliest,

imAnikFastest, 0.0s

rohijulislamLightest, 20 MB

kzvd4729Shortest, 678B

Login to submit