C++ or Java or any language

Maximizing the reward

You are given N tasks with following information:

Deadline: Di

Reward: Ri

Time taken to complete the tasks: Pi

The reward is given only when a task is completed within the corresponding deadline.

Write a program to schedule the tasks in order to maximize the reward.

Input format

First line: T (number of test cases)

First line in each test case: N

Next N lines in each test case: Three space-separated integers D_i, R_i, and P_i

Output format

For each test case, print the schedule of tasks that maximizes the reward in new line.

Constraints

1 T 10 1 N 10³ 1 D 10³ 1 P D 1 R 10⁶

Sample Input

1 6 1 2 1 2 3 1 4 1 2 10 10 10 15 13 10 15 7 5

Sample Output

20 

Explanation

If we perform the last two task alone we can get the maximum reward which is 20.

Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code will be run on multiple test cases. Therefore, your code must solve this problem statement.