#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

struct THING{char name[21];int vol;int need;};
struct PAIR{int x;int y;bool is;};
struct ANSWER{int sum;int num;char name[50][21];};

int CACHE[101][1001];
PAIR pairs[101][1001];
THING things[100];
ANSWER answer[50];
vector<int> ind;

/*
int mkCACHE(int n,int w){
    int i,&ret=CACHE[n][w];
    PAIR temp;
    if(ret==-1){
                if(n==0||w==0){ret=0;}
                else{
                     ret=mkCACHE(n-1,w);temp.x=n-1;temp.y=w;temp.is=false;
                     for(i=w-things[n-1].vol;i>=0;i--){
                                                       if(ret<mkCACHE(n-1,i)+things[n-1].need){
                                                                                               ret=mkCACHE(n-1,i)+things[n-1].need;
                                                                                               temp.x=n-1;temp.y=i;temp.is=true;
                     }}
                     pairs[n][w]=temp;
    }}
    return ret;
}
*/

int mkCACHE(int N,int W){
    int i,j,k;
    PAIR temp;
    for(i=0;i<=N;i++){
                      for(j=0;j<=W;j++){
                                        if(i==0||j==0){CACHE[i][j]=0;}
                                        else{
                                             CACHE[i][j]=CACHE[i-1][j];temp.x=i-1;temp.y=j;temp.is=false;
                                             for(k=0;k<=j-things[i-1].vol;k++){
                                                                               if(CACHE[i][j]<CACHE[i-1][k]+things[i-1].need){
                                                                                                                              CACHE[i][j]=CACHE[i-1][k]+things[i-1].need;
                                                                                                                              temp.x=i-1;temp.y=k;temp.is=true;
                                                                               }
                                             }
                                             pairs[i][j]=temp;
    }}}
    return CACHE[N][W];
}

void backtrack(PAIR temp){
     PAIR x=temp;
     while(x.x!=-1&&x.y!=-1){
                             if(x.is==true){ind.push_back(x.x);}
                             x=pairs[x.x][x.y];
     }
     return;
}

int main(void){
    int i,j,N,W,T;
    PAIR temp;
    cin>>T;
    for(i=0;i<T;i++){
                     cin>>N>>W;
                     for(j=0;j<=N;j++){memset(CACHE[j],-1,sizeof(int)*(W+1));}
                     for(j=0;j<=N;j++){
                                       for(int k=0;k<=W;k++){
                                               pairs[j][k].x=-1;pairs[j][k].y=-1;pairs[j][k].is=0;
                     }}
                     ind.clear();
                     for(j=0;j<N;j++){
                                      cin>>things[j].name;
                                      cin>>things[j].vol;
                                      cin>>things[j].need;
                     }
                     answer[i].sum=mkCACHE(N,W);
                     backtrack(pairs[N][W]);
                     answer[i].num=ind.size();
                     for(j=0;j<answer[i].num;j++){strcpy(answer[i].name[j],things[ind[j]].name);}
    }
    for(i=0;i<T;i++){
                     cout<<answer[i].sum<<' '<<answer[i].num<<endl;
                     for(j=answer[i].num-1;j>=0;j--){cout<<answer[i].name[j]<<endl;}
    }
    system("PAUSE");
    return 0;
}