#include <stdio.h>
#define LM 1004

int wi[104];
int pi[104];
int D[104][LM];
int path[104][LM];

int Max(int a, int b){if (a>b)return a; return b;}
int abs(int a) {if(a<0)return -a;return a;}

int ans[54][2];
int idx[54][104];
int name[54][104][34];

int main(){ 
   int C;   
   scanf("%d", &C); 
   for(int t = 1; t <= C; t++){     
       int N, W;        
       scanf("%d %d", &N, &W);      

       for(int i=0; i<=N; i++){
          for(int j=0; j<=W; j++){              
              D[i][j] = 1>>25;
              path[i][j]=-1;
          }
       }

       for(int i=1; i<=N; i++){         
          scanf("%s %d %d", name[t][i], wi+i, pi+i);        
       }        

       for(int i=1; i<=N; i++){         
          for(int j=0; j<=W; j++){
             if(j<wi[i]){                   
                D[i][j] = D[i-1][j];
                path[i][j]=-abs(path[i-1][j]);              }
            else if(j-wi[i]>=0){
                   if(D[i-1][j] > D[i-1][j-wi[i]]+pi[i]){
                   D[i][j] = D[i-1][j];
                   path[i][j]= -abs(path[i-1][j]);                 }
                else {
                   D[i][j] = D[i-1][j-wi[i]]+pi[i];
                   path[i][j] = abs(j-wi[i]);
                }
             }
          }
       }

       int pnt = W;
       int p = 0;   
       for(int i=N; i>=1; i--){
          if(path[i][pnt]>=0){
        idx[t][p++] = i;
        pnt = path[i][pnt];
        }
       }

       ans[t][0]=D[N][W];
       ans[t][1]=p; 
   }

   for(int t=1; t<=C; t++){
       if(ans[t][0] > 0){
      printf("%d %d\n", ans[t][0], ans[t][1]);             
      for(int i=ans[t][1]-1; i>=0; i--){
         printf("%s\n", name[t][idx[t][i]]);
      }
       }
   }
}