#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
const int M=3010;
int n,m,i,j,T,f[M];
struct node
{
    int x,y,z;
    double w;
}a[N];
int cmp(node a,node b)
{
    return a.w<b.w;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        for (i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            a[i].w=a[i].z*1.0/a[i].y;
        }
        sort(a+1,a+n+1,cmp);
        memset(f,-1,sizeof(f));
        for (f[0]=0,i=1;i<=n;i++)
            for (j=m;j>=a[i].z;j--)
                if (f[j-a[i].z]!=-1) f[j]=max(f[j],f[j-a[i].z]+a[i].x-a[i].y*j);
        for (i=0;i<m;i++) f[m]=max(f[m],f[i]);
        printf("%d\n",f[m]);
    }
    return 0;
}