I — Doing Homework

Ignatius has just come back to school from the 30th ACM ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 point for 1 day. As you know, doing homework always takes a long time. So Ignatius wants you to help him determine an ordering of his homework assignments that will minimize the reduced score.

Input Specification

The input contains several test cases. The first line of the input consists of a single integer T, which is the number of test cases. T test cases follow. Each test case starts with a positive integer N (1 ≤ N ≤ 15), indicating the number of homework assignments. Then N lines follow. Each line contains a string S (the subject's name, having at most 100 characters) and two integers D (the deadline of the subject's homework in days) and C (the number of days it takes Ignatius to finish this subject's homework).

Note: All subject names are given in alphabetically ascending order, so you can process the problem much easier.

Output Specification

For each test case, output the lowest total reduced score, then print the ordering of the subjects, one subject per line. If there is more than one ordering, output the alphabetically first one.

Sample Input

1. 2
2. 3
3. Computer 3 3
4. English 20 1
5. Math 3 2
6. 3
7. Computer 3 3
8. English 6 3
9. Math 6 3

download as text file

Output for Sample Input

1. 2
2. Computer
3. Math
4. English
5. 3
6. Computer
7. English
8. Math

download as text file

Hint

In the second test case, both Computer→English→Math and Computer→Math→English leads to a 3-point reduction, but the word “English” appears earlier than the word “Math”, so we choose the first ordering. This will result in the alphabetically first ordering.