Assignment Dilemma
Amir is a competitive programmer, very good one actually. He is also very successful in his academic life. He maintains the balance of contest programming and academic study by making proper use of his time. That’s why he is successful in both fields unlike a lot of his friends who failed to do this. But like every other University students, he often got overwhelmed by the assignments given by his course teachers. For example, He has 12 assignments this month, each of them with an specific deadline. Not only that, the grading system for the assignments is different too. For each assignments, you will get mark based on the following rule:
- If you submit your assignment X days before the deadline for that assignment you will get 10 marks for each X day. That means you will get 10*X marks for that assignment.
- If you submit your assignment X days after the deadline for that assignment you will get -10 marks for each X day. That means you will only get -10*X marks for that assignment.
- If you submit your assignment on the day of the deadline for that assignment you won’t get any marks. That means 0 for that assignment.
See, teachers will even give you NEGATIVE MARKS if you don’t finish your assignments in time. Don’t try to think what if “I don’t submit my assignments”, Don’t even think about it. That’s completely insane. You might get a huge punishment for that. So, that’s out of the question absolutely.
And Remember, you can’t do the assignments parallelly. You can’t do more than one assignments at a time and also you can’t start an assignment having your another assignment unfinished. You must finish one assignment before starting another. But it’s completely up to you in which order you want to do the assignments. Actually, that’s what you need to figure out to solve this problem.
Now back to the problem. As a good problem solver, Amir generally optimises his every work to gain the highest achievement. So, it won’t be a problem for him to devise a plan by algorithmic thinking that which assignments need to finish when to get the maximum number. We know he will do that. But can you? Well, if you want to be a good problem solver and a good student at the same time, like Amir, you should.
Input
First line will be a number T (1<=T<=1000), which will denote the number of test cases. Then followed T lines each with a number N (1<=N<=100), which will denote the number of assignments. Following each of the N lines will consists the string denoting the name of the assignment A (single word, consists only alphanumeric characters and underscore), days required to finish this assignment F(0<F<2^31) and the deadline D(0<D<2^31). The deadline will be counted in days. Like if the deadline is given as 10 that means today is the day 0 and the assignment needs to be completed within 10 days. All the deadlines will be started counting at the same time, from the day 0.
Same assignments won’t be given twice in a single Test case. So you can assume that each of the assignments name will be unique in a single Test case.
Output
For each test case, output the maximum marks you can get by completing the assignments.
Sample
| Input | Output |
|---|---|
1 3 operating_system 2 5 data_communication 5 10 math_for_CS 8 8 | -10 |
Explanation:
The most optimal way to achieve the highest mark for the given test case is to submit the assignments in the following order:
Assignment 1 (deadline in 5 days, completed in 2 days. So, achievement: 3*10 = 30 marks)
Assignment 2 (deadline in 10 days, completed in 7 days. So, achievement: 3*10 = 30 marks)
Assignment 3 (deadline in 8 days, completed in 15 days. So, achievement: -7*10 = -70 marks)
Total = 30 + 30 + (-70)
= -10
