#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <utility>
#include <math.h>
#include <cstdlib>
#include <memory.h>
#include <queue>
#define pb push_back
#define i64 long long
#define mp make_pair
#define pii pair <int,int>
#define vi vector <int>
#define vii vector <pii>
#define f first
#define s second
#define foran(i,a,b) for (int i=a;i<(int)b;i++)
#define forn(i,n) for (int i=0;i<(int)n;i++)
#define ford(i,n) for (int i=(int)n-1;i>=0;i--)
#define sqr(x) (x) * (x)
const double eps = 1e-9;
const int int_inf = 1 << 31 - 1;
const i64 i64_inf = 1ll << 63 - 1;
const double pi = acos(-1.0);
using namespace std;
vector < pair <int,i64> > a[2];
int n, m;
int W[20]; int C[20];
int T;
i64 res;
void build(int l, int r, int to) //a[to][i] -> pair <W, C>
{
for (int i = l; i <= r; i++)
{
int sz = (int)a[to].size();
forn(j, sz)
forn(c, i + 2)
a[to].pb( mp(a[to][j].f + (i64)c * W[i], a[to][j].s + (i64)c * C[i]) );
forn(c, i + 2)
a[to].pb( mp((i64)c * W[i], (i64)c * C[i]) );
}
sort(a[to].begin(), a[to].end());
}
i64 solve()
{
a[0].clear(); a[1].clear();
build(0, min(9, n - 1), 0);
if (n <= 10)
{
forn(i, a[0].size())
if (a[0][i].f <= m) res = max(res, a[0][i].s); else break;
return res;
}
build(10, n - 1, 1);
i64 ma = 0;
forn(i, a[1].size())
ma = max(a[1][i].s, ma), a[1][i].s = ma;
int r = (int)a[1].size() - 1;
forn(i, a[0].size())
{
while (r >= 0 && a[1][r].f + a[0][i].f > m) r--;
if (a[1][r].f + a[0][i].f > m) break;
res = max(res, a[1][r].s + a[0][i].s);
}
return res;
}
int main() {
cin >> T;
forn(TT, T)
{
scanf("%d%d", &n, &m);
forn(i, n)
scanf("%d", &W[i]);
forn(i, n)
scanf("%d", &C[i]);
res = 0;
printf("%I64d\n", solve());
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8bWVtb3J5Lmg+CiNpbmNsdWRlIDxxdWV1ZT4KCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgaTY0IGxvbmcgbG9uZwojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBpaSBwYWlyIDxpbnQsaW50PgojZGVmaW5lIHZpIHZlY3RvciA8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3IgPHBpaT4KI2RlZmluZSBmIGZpcnN0CiNkZWZpbmUgcyBzZWNvbmQKI2RlZmluZSBmb3JhbihpLGEsYikgZm9yIChpbnQgaT1hO2k8KGludCliO2krKykKI2RlZmluZSBmb3JuKGksbikgZm9yIChpbnQgaT0wO2k8KGludCluO2krKykKI2RlZmluZSBmb3JkKGksbikgZm9yIChpbnQgaT0oaW50KW4tMTtpPj0wO2ktLSkKI2RlZmluZSBzcXIoeCkgKHgpICogKHgpCgpjb25zdCBkb3VibGUgZXBzID0gMWUtOTsKY29uc3QgaW50IGludF9pbmYgPSAxIDw8IDMxIC0gMTsKY29uc3QgaTY0IGk2NF9pbmYgPSAxbGwgPDwgNjMgLSAxOwpjb25zdCBkb3VibGUgcGkgPSBhY29zKC0xLjApOwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvciA8IHBhaXIgPGludCxpNjQ+ID4gYVsyXTsKaW50IG4sIG07CmludCBXWzIwXTsgaW50IENbMjBdOwppbnQgVDsKCmk2NCByZXM7Cgp2b2lkIGJ1aWxkKGludCBsLCBpbnQgciwgaW50IHRvKSAvL2FbdG9dW2ldIC0+IHBhaXIgPFcsIEM+CnsKIGZvciAoaW50IGkgPSBsOyBpIDw9IHI7IGkrKykKIHsKICAgICBpbnQgc3ogPSAoaW50KWFbdG9dLnNpemUoKTsKICAgICBmb3JuKGosIHN6KQogICAgICBmb3JuKGMsIGkgKyAyKQogICAgICAgYVt0b10ucGIoIG1wKGFbdG9dW2pdLmYgKyAoaTY0KWMgKiBXW2ldLCBhW3RvXVtqXS5zICsgKGk2NCljICogQ1tpXSkgKTsKICAgICBmb3JuKGMsIGkgKyAyKQogICAgICBhW3RvXS5wYiggbXAoKGk2NCljICogV1tpXSwgKGk2NCljICogQ1tpXSkgKTsKIH0KIHNvcnQoYVt0b10uYmVnaW4oKSwgYVt0b10uZW5kKCkpOwp9CgppNjQgc29sdmUoKQp7CiAgICAgYVswXS5jbGVhcigpOyBhWzFdLmNsZWFyKCk7CiAgICAgYnVpbGQoMCwgbWluKDksIG4gLSAxKSwgMCk7CgogICAgIGlmICAobiA8PSAxMCkKICAgICB7CiAgICAgICAgIGZvcm4oaSwgYVswXS5zaXplKCkpCiAgICAgICAgICBpZiAgKGFbMF1baV0uZiA8PSBtKSByZXMgPSBtYXgocmVzLCBhWzBdW2ldLnMpOyBlbHNlIGJyZWFrOwogICAgICAgICByZXR1cm4gcmVzOwogICAgIH0KCiAgICAgYnVpbGQoMTAsIG4gLSAxLCAxKTsKCiAgICAgaTY0IG1hID0gMDsKICAgICBmb3JuKGksIGFbMV0uc2l6ZSgpKQogICAgICBtYSA9IG1heChhWzFdW2ldLnMsIG1hKSwgYVsxXVtpXS5zID0gbWE7CgogICAgIGludCByID0gKGludClhWzFdLnNpemUoKSAtIDE7CgogICAgIGZvcm4oaSwgYVswXS5zaXplKCkpCiAgICAgewogICAgICAgIHdoaWxlIChyID49IDAgJiYgYVsxXVtyXS5mICsgYVswXVtpXS5mID4gbSkgci0tOwogICAgICAgIGlmICAoYVsxXVtyXS5mICsgYVswXVtpXS5mID4gbSkgYnJlYWs7CiAgICAgICAgcmVzID0gbWF4KHJlcywgYVsxXVtyXS5zICsgYVswXVtpXS5zKTsKICAgICB9CiAgICAgcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKSB7CiAgY2luID4+IFQ7CiAgZm9ybihUVCwgVCkKICB7CiAgICAgIHNjYW5mKCIlZCVkIiwgJm4sICZtKTsKCiAgICAgIGZvcm4oaSwgbikKICAgICAgIHNjYW5mKCIlZCIsICZXW2ldKTsKICAgICAgZm9ybihpLCBuKQogICAgICAgc2NhbmYoIiVkIiwgJkNbaV0pOwoKICAgICAgcmVzID0gMDsKICAgICAgcHJpbnRmKCIlSTY0ZFxuIiwgc29sdmUoKSk7CiAgfQogIHJldHVybiAwOwp9Cg==