#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<cctype> #include<queue> using namespace std; int n,base[20]; struct node { char name[111]; int dead,cost; }MEM[20]; struct node1 { int days,score; int pre,now; }DP[1<<15]; int main() { int T; int i,l; int tot,t,reduce; for(i=0;i<15;i++) base[i]=1<<i; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%s %d %d",MEM[i].name,&MEM[i].dead,&MEM[i].cost); memset(DP,127,sizeof(DP)); DP[0].days=0; DP[0].score=0; DP[0].pre=-1; tot=1<<n; for(i=0;i<tot;i++) { for(l=n-1;l>=0;l--)//从大到小,并且在后面的第七行用了“<”:保证顺序 { if(i & base[l]) { t=i-base[l]; reduce=DP[t].days+MEM[l].cost-MEM[l].dead; if(reduce<0) reduce=0; if(DP[t].score+reduce<DP[i].score) { DP[i].pre=t; DP[i].now=l; DP[i].days=DP[t].days+MEM[l].cost; DP[i].score=DP[t].score+reduce; } } } } int K=0,temp=(1<<n)-1; char ans[20][111]; while(DP[temp].pre!=-1) { strcpy(ans[K++],MEM[DP[temp].now].name); temp=DP[temp].pre; } printf("%d\n",DP[(1<<n)-1].score); for(i=K-1;i>=0;i--) printf("%s\n",ans[i]); } return 0; }