1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 #define inf 0x7ffffff
 8 struct homework{
 9     char name[110];
10     int dl;
11     int ct;
12     int no;//輸出序列
13     int temp;//臨時標記
14 };
15 homework hw[20];
16 int dp[40000];
17 int n,cas,min_reduce;
18 int cmp(homework a,homework b){
19     return a.no<b.no;
20 }
21 void dfs(int steps,int score,int day,int now){
22     //課程完成數、當前搜索深度的扣分值，當前消耗的天數，當前的狀態
23     int i;
24     if(steps==n){
25         if(score<min_reduce){
26             min_reduce=score;
27             for(i=0;i<n;i++)
28                 hw[i].no=hw[i].temp;
29         }
30         return ;
31     }
32     if(dp[now]>score)//此處的剪枝很關鍵 判斷此課程是否之前已存在最優解
33         dp[now]=score;
34     else
35         return ;
36     for(i=0;i<n;i++){
37         if(hw[i].temp)
38             continue;
39         hw[i].temp=steps+1;//記錄順序
40         int cost=0;
41         if(hw[i].ct+day>hw[i].dl)//扣分
42             cost=hw[i].ct+day-hw[i].dl;
43         dfs(steps+1,score+cost,day+hw[i].ct,now+(1<<i));//下一課程
44         hw[i].temp=0;//記憶化搜索
45     }
46 }
47 int main(){
48     //freopen("in.txt","r",stdin);
49     int i;
50     scanf("%d",&cas);
51     while (cas--){
52         scanf("%d",&n);
53         for(i=0;i<n;i++){
54             getchar();
55             scanf("%s %d %d",&hw[i].name,&hw[i].dl,&hw[i].ct);
56             hw[i].no=hw[i].temp=0;
57         }
58         for(i=0;i<40000;i++)
59             dp[i]=inf;
60         //由截止日期與開銷決定作業完成先后次序，如何判定優先級
61         min_reduce=inf;
62         dfs(0,0,0,0);
63         sort(hw,hw+n,cmp);
64         printf("%d\n",min_reduce);
65         for(i=0;i<n;i++)
66             printf("%s\n",hw[i].name);
67     }
68     return 0;
69 }
70