#include <stdio.h>

#define MAX(x, y) (x)>(y)?(x):(y)

typedef struct _stuffInfo{
    char name[25];
    int volume;
    int howMuchNeeded;
}StuffInfo;

int N, W;
StuffInfo stuff[105];
int cache[105][1005];
int selectedStuffIdx[105];
int selectedStuffCnt;

void init(void);
void input(void);
void solve(void);
int solving(int stuffIdx, int leftVolumeOfBag);
void findSelctedStuff(int stuffIdx, int leftVolumeOfBag);

int main(void)
{
    int tc, T;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    for (tc = 1; tc <= T; tc++)
    {
        input();
        init();
        solve();
    }

    return 0;
}

void init(void)
{
    selectedStuffCnt = 0;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= W; j++)
            cache[i][j] = -1;
    }
}

void input(void)
{
    scanf("%d%d", &N, &W);
    for (int i = 1; i <= N; i++)
        scanf("%s%d%d", stuff[i].name, &stuff[i].volume, &stuff[i].howMuchNeeded);
}

void solve(void)
{
    int howMuchNeededMaxValue = 0;

    howMuchNeededMaxValue = solving(0, W);
    findSelctedStuff(0, W);

    printf("%d %d\n", howMuchNeededMaxValue, selectedStuffCnt);
    for (int i = 0; i < selectedStuffCnt; i++)
    {
        for (int j = 0; stuff[selectedStuffIdx[i]].name[j] != 0; j++)
                printf("%c", stuff[selectedStuffIdx[i]].name[j]);
        puts("");
    }
}
//stuffIdx 이후 물건들 고려(남은 용량이 leftVolumeOfBag)했을 때, 최대 절박도
int solving(int stuffIdx, int leftVolumeOfBag)
{
    //기저 사례
    if (N == stuffIdx)
        return 0;

    int& ret = cache[stuffIdx][leftVolumeOfBag];

    if (ret != -1)
        return ret;

    ret = solving(stuffIdx + 1, leftVolumeOfBag);
    //가방 보다 부피 커지는 것 넣으면 안됨 + 물건이 1개인 경우, 해당 물건의 부피가 가방의 부피보다 큰 경우 0 찍어 줘야 함.
    if (leftVolumeOfBag - stuff[stuffIdx].volume >= 0)
        ret = MAX(ret, solving(stuffIdx + 1, leftVolumeOfBag - stuff[stuffIdx].volume) + stuff[stuffIdx].howMuchNeeded);

    return ret;
}

void findSelctedStuff(int stuffIdx, int leftVolumeOfBag)
{
    if (stuffIdx == N)
        return;

    if (solving(stuffIdx, leftVolumeOfBag) == solving(stuffIdx + 1, leftVolumeOfBag))
        findSelctedStuff(stuffIdx + 1, leftVolumeOfBag);
    else
    {
        selectedStuffIdx[selectedStuffCnt] = stuffIdx;
        selectedStuffCnt += 1;
        findSelctedStuff(stuffIdx + 1, leftVolumeOfBag - stuff[stuffIdx].volume);
    }
}