IPC Trainers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
During the Indian Programming Camp (IPC), there are N trainers. The camp runs for D days. Each day, there can be at most one lecture. The ith trainer arrives on day D_{i} and then stays till the end of the camp. He also wants to teach exactly Ti lectures. For each lecture that a trainer was not able to teach, he will feel sad and his sadness level will be increased by S_{i}.
You are the main organizer of the contest. You want to find minimum total sadness of the trainers.
Input
The first line of the input contains an integer T, denoting the number of testcases.
For each test case, the first line contains two space separated integers, N, D.
The ith of the next N lines will contain three space separated integers: D_{i}, T_{i}, S_{i} respectively.
Output
For each test case, output a single integer corresponding to the minimum total sadness of the trainers achievable.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, D ≤ 10^{5}
 1 ≤ D_{i}, T_{i} ≤ D
 1 ≤ S_{i} ≤ 10^{5}
Subtasks
Subtask #1 (40 points)
 1 ≤ T ≤ 10
 1 ≤ N, D ≤ 10^{3}
 1 ≤ D_{i}, T_{i} ≤ D
 1 ≤ S_{i} ≤ 10^{3}
Subtask #2 (60 points)
 Original constraints
Example
Input 3 2 3 1 2 300 2 2 100 2 3 1 1 100 2 2 300 2 3 3 2 150 1 1 200 Output 100 0 150
Explanation
Example case 1. Both the first and second trainer want to take exactly two lectures. The first trainer arrives on the 1st day and the second trainer arrives on the 2nd day. Consider a schedule where the first trainer takes the first two lectures, and the second trainer takes the last lecture on the day 3. This way the second trainer will take only one lecture but wanted to take two. Thus, his sadness will be 100. The first trainer took all the lectures that he wanted to take (ie. two lectures). Thus the total sadness is 100 + 0 = 100. You can check that no other way of assigning trainers to the days will give a better answer than this.
Example case 2. In this case, the trainers can all take all their ideal number of lectures.
Example case 3. In this case, the first trainer arrives on day 3 and wants to take two lectures. This is not possible as he can take at most one lecture on day 3 and the camp ends on day 3. The second trainer wants to take only one lecture which he can take on any one of the 1st or 2nd days. You can see that in one of the first or second days, no lecture will be held.
Author:  admin2 
Editorial  https://discuss.codechef.com/problems/IPCTRAIN 
Tags  admin2, easy, greedy, heap, july17, stl 
Date Added:  5072017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions