//三维待优化
//内存超限

//AC
#include<bits/stdc++.h>

using namespace std;
const int N=600+10;

int f[N][N][2];
int t,n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        int res=0;
        memset(f,0xcf,sizeof f);
        f[0][0][0]=0,f[0][0][1]=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            for(int j=0;j<=m;j++)
            {
                if(j>=a)f[i][j][0]=max(f[i-1][j-a][0],f[i-1][j-a][1])+b;
                if(j>=c)f[i][j][1]=max(f[i-1][j-c][0],f[i-1][j-c][1])+d;
                res=max(f[i][j][1],max(res,f[i][j][0]));
            }
        }
        cout<<res<<endl;
    }

}