var
  cas,xx,n,m,i,j:longint;
  ans:int64;
  a,b,c,f:array[0..10010]of int64;
  procedure swap(var x,y:int64);
    var
      z:int64;
      begin
        z:=x; x:=y; y:=z;
      end;
  function min(x,y:longint):longint;
    begin
      if x<y then min:=x else min:=y;
    end;
  procedure qsort(l,r:longint);
    var
      i,j:longint;
      mid,mid1,p:int64;
      begin
        i:=l; j:=r; mid:=b[(l+r) div 2]; mid1:=c[(l+r) div 2];
        repeat
          while b[i]*mid1>c[i]*mid do inc(i);
          while b[j]*mid1<c[j]*mid do dec(j);
          if i<=j then
            begin
              swap(a[i],a[j]);
              swap(b[i],b[j]);
              swap(c[i],c[j]);
              inc(i); dec(j);
            end;
        until i>j;
        if l<j then qsort(l,j);
        if i<r then qsort(i,r);
      end;
  begin
    readln(cas);
    for xx:=1 to cas do
      begin
        readln(n,m);
        for i:=1 to n do readln(a[i],b[i],c[i]);
        qsort(1,n);
        fillchar(f,sizeof(f),$8f);
        f[0]:=0;
        for i:=1 to n do
          for j:=min(m,a[i] div b[i]) downto c[i] do
            if f[j-c[i]]+a[i]-j*b[i]>f[j] then f[j]:=f[j-c[i]]+a[i]-j*b[i];
        ans:=0;
        for i:=1 to m do
          if f[i]>ans then ans:=f[i];
        writeln(ans);
      end;
  end.