/*狀壓dpD - Doing Homework時間: 2017/02/20題意：作業超過時限，超過一天扣一分，給出n個作業及其時限和需要完成的時間，求最小扣分值和其路徑題解：狀態壓縮dp，本應該要想到的。其N<=15，根據選沒選壓成二進制因為題目要求最后方案如果多個情況以字典序排序，所以可以先將原數據先排序然后我們發現遞歸時缺少了上一個狀態的所用時間，我先預處理出來。設這個狀態為wi,上個狀態為wj,這個狀態和上個狀態相差的那個作業的編號為id那么 dp[wi] = dp[wj]+time[wj]+C[id]-D[id]。*/#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<queue>#include<map>using namespace std;#define N 110#define INF 0x3f3f3f3fstruct asd{    char name[N];    int a,b;}node[20];bool cmp(asd x,asd y){    return strcmp(x.name,y.name)>0;}int dp[1<<15],time[1<<15],PRe[1<<15];int main(){    int T;    scanf("%d",&T);    while(T--)    {        memset(dp,0,sizeof(dp));        memset(pre,0,sizeof(pre));        memset(time,0,sizeof(time));        int n;        scanf("%d",&n);        for(int i = 0; i < n; i++)            cin >> node[i].name >> node[i].a >> node[i].b;        sort(node,node+n,cmp);        for(int i = 1; i < 1<<n; i++)        {             for(int j = i; j > 0; j -= (j&-j))             {                int k = j&-j,num = 1;                while(k>>num)                    num++;                time[i] += node[num-1].b;             }        }        for(int i = 1; i < 1<<n; i++)        {            dp[i] = INF;            for(int j = i; j > 0; j -= (j&-j))            {                int k = j&-j,num = 1;                while(k>>num)                    num++;                int ans = time[i & ~(j&-j)]+node[num-1].b-node[num-1].a;                ans = ans<0?0:ans;//                dp[i] = min(dp[i],dp[i & ~(j&-j)] + ans);                if(dp[i] > dp[i & ~(j&-j)]+ans)                {                    dp[i] = dp[i & ~(j&-j)]+ans;                    pre[i] = num-1;                }            }        }        printf("%d/n",dp[(1<<n)-1]);        int val = (1<<n)-1;        int res[20];        int id = 0;        while(1)        {            res[id++] = pre[val];            //printf("%s/n",node[pre[val]].name);            val -= 1 << pre[val];            if(val == 0)                break;        }        for(int i = id-1; i >= 0; i--)            printf("%s/n",node[res[i]].name);    }    return 0;}