分析
状压dp显然，主要是字典序的问题，
考虑初态终态转换就可以保证字典序最小了
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
const int N=21,M=1050011; char s[N][N*3];
int pre[M],dp[M],n,lim[N],two[N],a[N],sum[M],cho[M];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
signed main(){
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
two[0]=1;
for (rr int i=1;i<21;++i) two[i]=two[i-1]<<1;
for (rr int i=0;i<21;++i) cho[two[i]]=i;
for (rr int T=iut();T;--T){
n=iut();
for (rr int i=n-1;~i;--i){
scanf("%s",s[i]+1);
lim[i]=iut(),a[i]=iut();
}
memset(dp,42,sizeof(dp)),dp[two[n]-1]=0;
for (rr int S=1;S<two[n];++S)
sum[S]=sum[S&(S-1)]+a[cho[-S&S]];
for (rr int S=two[n]-1;S;--S){
for (rr int j=S;j;j&=j-1){
rr int i=cho[-j&j],t=0;
if (sum[S]>=lim[i]) t=sum[S]-lim[i];
if (dp[S^two[i]]>dp[S]+t)
dp[S^two[i]]=dp[S]+t,pre[S^two[i]]=i;
}
}
printf("%d
",dp[0]);
for (rr int S=0;S!=two[n]-1;S^=two[pre[S]])
printf("%s
",s[pre[S]]+1);
}
return 0;
}