#include<iostream>#include<sstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>using namespace std;const double eps(1e-8);typedef long long lint;#define clr(x) memset( x , 0 , sizeof(x) )#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clrs( x , y ) memset( x , y , sizeof(x) )int n, m, t1[111], t2[111], t3[111], f1[111], f3[111];int f[111][111];int main() { int t; scanf("%d", &t); while (t --) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++) scanf("%d%d%d%d%d", &t1[i], &t2[i], &t3[i], &f1[i], &f3[i]); memset(f, -1, sizeof(f)); f[0][m] = 0; for (int i = 0; i <= n - 1; i ++) for (int j = 0; j <= m; j ++) { if (f[i][j] == -1) continue; if (j >= f1[i + 1] && (f[i + 1][j - f1[i + 1]] == -1 || f[i][j] + t1[i + 1] < f[i + 1][j - f1[i + 1]])) f[i + 1][j - f1[i + 1]] = f[i][j] + t1[i + 1]; if (f[i + 1][j] == -1 || f[i][j] + t2[i + 1] < f[i + 1][j]) f[i + 1][j] = f[i][j] + t2[i + 1]; int tmp = min(j + f3[i + 1], m); if (f[i + 1][tmp] == -1 || f[i][j] + t3[i + 1] < f[i + 1][tmp]) f[i + 1][tmp] = f[i][j] + t3[i + 1]; } int ans = 1000000000; for (int i = 0; i <= m; i ++) if (f[n][i] != -1) ans = min(ans, f[n][i]); cout <<ans<<endl; } return 0;}
