OpenJudge

09:Project Deadline

总时间限制:
1000ms
内存限制:
65536kB
描述

Xiaoming is currently a third year undergraduate student in School of EECS, Peking University. He likes participating various community in the campus such as chess, biking, etc. This semester is coming to the end and the deadline of the project for each course is approaching. However, Xiaoming has NOT started working any project yet. Every course has a project and every project has a deadline. If Xiaoming fails to submit his project on time, he will be penalized. In particular, if he submits his project X days after the deadline, he will be penalized by X points. For each project, Xiaoming needs to spend one or a few days to finish it. He only can start a new project before he finishes the current one. Before Xiaoming starts to work on his projects, he would like you to help him to figure out the best way (the order to finish the projects) to minimize the penalty.

输入
The input contains several test cases.
The first line of the input is a single integer T, which is the number of test cases.
T test cases follow. Each test case start with a positive integer N (1 <= N <= 15), which is the number of courses.
Then, N lines follow. Each line contains a string S (the course name, S contains no more than 50 characters) and two integers D (the deadline of the course), C (the number of days that Xiaoming needs to finish this project).
Note that all the course are in alphabet increasing order in the input.
输出
For each test case, you should output the smallest total penalty, then output the order of the courses, one course in a line. If there are more than one orders, you should output the one with small alphabet order.
样例输入
2 
3 
Computer 3 3 
English 20 1 
Math 3 2 
3
Computer 3 3 
English 6 3 
Math 6 3
样例输出
2 
Computer 
Math 
English 
3 
Computer 
English 
Math
提示
For the second test case, both Computer->English->Math and Computer->Math->English leads to 3 points penalty, but the word "English" appears earlier than the word "Math", so we choose the first order (alphabet order).

01 Use "long long" to calculate the answer
05 Expected Value of an Expression: Ai is less than 2^20

全局题号
15302
提交次数
14
尝试人数
7
通过人数
2