#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;
}