#include<iostream>
using namespace std;
int a[1111],b[111],c[111];
int cost[111],earn[111];
int dp[111][111];//记录到第i个栏还有能量j的最短时间
int getMin(int a,int b)
{
if(a < b)
return a;
else
return b;
}
int main()
{
int text;
cin>>text;
while(text--)
{
int n,m;
int i,j;
cin>>n>>m;
for(i = 0; i < n;i++)
{
cin>>a[i]>>b[i]>>c[i]>>cost[i]>>earn[i];
}
for(i = 0;i <111;i++)
for(j = 0;j < 111;j++)
dp[i][j] = 100000000;
dp[0][m] = 0;
for(i = 0;i < n;i++)//栏的个数
for(j = 0;j <= m;j++)//剩余时间
{
if(j >= cost[i])//剩余时间大于最快速度花费的时间
dp[i+1][j-cost[i]] = getMin(dp[i+1][j-cost[i]],dp[i][j] + a[i]);
if(j+earn[i] > m)//剩余时间加上最慢时间所给时间大于m
dp[i+1][m] = getMin(dp[i+1][m],dp[i][j] + c[i]);
else//不大于m
dp[i+1][j+earn[i]] = getMin(dp[i+1][j+earn[i]],dp[i][j]+c[i]);
dp[i+1][j] = getMin(dp[i+1][j],dp[i][j]+b[i]);//以正常速度跑步
}
int mins = 100000000;
for(i = 0;i <= m;i++)//选择最小时间
{
if(mins > dp[n][i])
mins = dp[n][i];
}
cout<<mins<<endl;
}
return 0;
}