1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int const INF = 0x3f3f3f3f;
 8 int const MAX = (1<<15) + 10;
 9 int pre[MAX],dp[MAX], t[MAX];
10 char s[20][110];
11 
12 void print(int n) {//存储时候从后往前，所以输出时，先递归进行输出,从后往前输出
13     if(n == 0) return ;
14     print(n-(1 << pre[n]));
15     printf("%s\n",s[pre[n]]);
16 }
17 int main()
18 {
19     int T,n;
20     int dl[20],dr[20];
21     while(scanf("%d",&T) != EOF) {
22         while(T--){
23             scanf("%d",&n);
24             for(int i = 0;i < n; i++)
25                 scanf("%s%d%d",s[i],&dl[i],&dr[i]);
26             int w = 1<<n;
27             for(int i = 1; i < w; i++) {//从1种到1<<n种情况进行枚举
28                 dp[i] = INF;
29                 for(int j = n-1 ; j >=0 ;j--) {//用二进制表示选用第几个的情况
30                     int cnt = 1 << j;
31                     if( !(i&cnt))continue;//没有选用第j个
32                     int score = t[i - cnt] - dl[j] + dr[j];
33                     if(score < 0) score = 0;//分数小于0说明没有超出时限
34                     if(dp[i] > dp[i-cnt] + score) {
35                         dp[i] = dp[i-cnt] +score;
36                         t[i] = t[i-cnt] + dr[j];
37                         pre[i] = j;
38                     }
39                 }
40             }
41             printf("%d\n",dp[w-1]);
42             print(w-1);
43         }
44     }
45     return 0;
46 }