A.作业

A.作业

Background

Special for beginners, ^_^

【问题描述】
小z是某高中的一名学生。他在欢乐地度过暑假的时候,突然发现他有些作业的截止时间快到了。但是小z还没开始做。如果一个作业,小z提交时间超过截止时间X天,那么他就会被扣掉X分。对于每个作业,小z要花费一天或若干天来完成。他不能同时完成多个作业且只有当前作业完成了,他才会开始另一个新的作业。小z不想被扣太多分,所以他想知道如果规划完成作业的顺序使得被扣掉的分最少。

【输入格式】
输入多组数据。
输入第一行为一个整数T,表示数据组数。
对于每组数据,第一行为一个整数n,表示课程数目。
接下来n行,每行包含一个字符串S(不多于50个字符)代表课程名称和两个整数D(截止时间)和C(完成作业需要时间)

【输出格式】
对于每组数据,第一行输出最少扣分。
接下来n行,输出完成作业的顺序。

输入样例

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

Limitation

2s, 256MiB for each test case.

【数据范围与约定】
30%: n <= 10
60%: n <= 17
100%: n <= 20, T <= 3