http://acm.hdu.edu.cn/showproblem.php?pid=1074
//1311853 2009-04-26 19:16:12 Accepted 1074 281MS 524K 1323 B C++ no way 
#include<iostream>
#include<string>
using namespace std;
struct Node
{
    string course;
    int deadline;
    int need;
}infor[16];
int n;
int binary[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
int flag[65536];
bool mark[16];
string str[16],outs[16];
void dfs(int days,int cost,int sum,int num)//num表示选择的作业数
{ //days表示写作业的开始日期，cost表示前面的花费，sum记录作业是否完成情况
    int i,temp;
    if(num == n)
    {
        if(flag[sum] == cost)
        {
            flag[sum] = cost;
            for(i=0;i<num;i++)
                outs[i] = str[i];
        }
        return ;
    }
    for(i=1;i<=n;i++)
    {
        if(mark[i] == false)
        {
            mark[i] = true;
            sum += binary[i];//要写第i门作业
           ///////////////////////////////////////////////////
            temp = days + infor[i].need - infor[i].deadline;
            if(temp < 0)
                temp = cost;
            else
                temp += cost;
           //  第i门作业完成后的代价 temp
           //////////////////////////////////////
            if(flag[sum] > temp)
            {
                flag[sum] = temp; //记录状态

                str[num++] = infor[i].course;

                dfs(days + infor[i].need,temp,sum,num);

                num --;
            }
            sum -= binary[i];
            mark[i] = false;
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {        
        int i,st=0;
        cin>>n;
        for(i=1;i<=n;i++)
            cin>>infor[i].course>>infor[i].deadline>>infor[i].need;
        for(i=0;i<65536;i++)
            flag[i] = 1000000;
        memset(mark,false,sizeof(mark));//标记状态
        dfs(0,0,0,0);
        for(i=1;i<=n;i++)
            st += binary[i];  //结果存放在下标为st的flag[st]值中
        cout<<flag[st]<<endl;
        for(i=0;i<n;i++)
            cout<<outs[i]<<endl;
    }
    return 0;
}