Polycarp often uses his smartphone. He has already installed n applications on it. Application with number i takes up a_i units of memory.

Polycarp wants to free at least m units of memory (by removing some applications).

Of course, some applications are more important to Polycarp than others. He came up with the following scoring system — he assigned an integer b_i to each application: 

  * b_i = 1 — regular application; 
  * b_i = 2 — important application. 



According to this rating system, his phone has b_1 + b_2 + … + b_n convenience points.

Polycarp believes that if he removes applications with numbers i_1, i_2, …, i_k, then he will free a_{i_1} + a_{i_2} + … + a_{i_k} units of memory and lose b_{i_1} + b_{i_2} + … + b_{i_k} convenience points.

For example, if n=5, m=7, a=[5, 3, 2, 1, 4], b=[2, 1, 1, 2, 1], then Polycarp can uninstall the following application sets (not all options are listed below): 

  * applications with numbers 1, 4 and 5. In this case, it will free a_1+a_4+a_5=10 units of memory and lose b_1+b_4+b_5=5 convenience points; 
  * applications with numbers 1 and 3. In this case, it will free a_1+a_3=7 units of memory and lose b_1+b_3=3 convenience points. 
  * applications with numbers 2 and 5. In this case, it will free a_2+a_5=7 memory units and lose b_2+b_5=2 convenience points. 



Help Polycarp, choose a set of applications, such that if removing them will free at least m units of memory and lose the minimum number of convenience points, or indicate that such a set does not exist.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 10^9) — the number of applications on Polycarp's phone and the number of memory units to be freed.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — the number of memory units used by applications.

The third line of each test case contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ 2) — the convenience points of each application.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output on a separate line: 

  * -1, if there is no set of applications, removing which will free at least m units of memory; 
  * the minimum number of convenience points that Polycarp will lose if such a set exists. 

Example

Input


5
5 7
5 3 2 1 4
2 1 1 2 1
1 3
2
1
5 10
2 3 2 3 2
1 2 1 2 1
4 10
5 1 3 4
1 2 1 2
4 5
3 2 1 2
2 1 2 1


Output


2
-1
6
4
3

Note

In the first test case, it is optimal to remove applications with numbers 2 and 5, freeing 7 units of memory. b_2+b_5=2.

In the second test case, by removing the only application, Polycarp will be able to clear only 2 of memory units out of the 3 needed.

In the third test case, it is optimal to remove applications with numbers 1, 2, 3 and 4, freeing 10 units of memory. b_1+b_2+b_3+b_4=6.

In the fourth test case, it is optimal to remove applications with numbers 1, 3 and 4, freeing 12 units of memory. b_1+b_3+b_4=4.

In the fifth test case, it is optimal to remove applications with numbers 1 and 2, freeing 5 units of memory. b_1+b_2=3.
#include <bits/stdc++.h>

#define optimize ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define S second
#define F first
#define ENDL '\n'
#define fori(i, n) for(int i=0; i<n; ++i)
#define foreach(n) for(int i=0; i<n; ++i)
#define read_v(v) for(int i=0; i<v.size(); ++i) cin >> v[i]
#define all(v) v.begin(), v.end()
#define asc_sort(v) sort(v.begin(), v.end())
#define desc_sort(v) sort(v.rbegin(), v.rend())
#define print_all(v) for(int i=0; i<(int)v.size(); ++i) cout << v[i] << (i<(int)v.size()-1 ? ' ' : '\n')
#define pb push_back
#define sz(v) v.size()
#define ceil_div(a, b) (a+b-1) / b
#define tcs(foo)  {                   \
                  int tc;             \
                  cin >> tc;          \
                  while(tc--) foo();  \
                  }

using namespace std;

typedef string str;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<bool> vbool;
typedef vector<long long> vll;
typedef vector<unsigned long long> vull;
typedef vector<string> vstr;
typedef vector<pair<int, int>> vpii;
typedef set<int> s_int;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> min_heap;
typedef priority_queue<int> max_heap;

string to_string(string s) { return '"' + s + '"'; }

string to_string(const char* s) { return to_string((string) s); }

string to_string(bool b) { return (b ? "true" : "false"); }

template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

/********************
    END TEMPLATE
*********************/
ll n, m, ans, sm, suma, sumb;

void solve(){
  cin >> n >> m;
  vi A, B, tmp(n);
  int aux, i, j;
  suma = sumb = sm  = 0;
  ans = INT_MAX;

  read_v(tmp);

  for(auto &a : tmp){
    cin >>  aux;
    sm += a;
    if(aux==1) {
      A.pb(a);
    }else {
      sumb += a;
      B.pb(a);
    }
  }

  if(sm < m){
    cout << -1 << endl;
    return;
  }

  desc_sort(A);
  desc_sort(B);

  i = 0;
  j = sz(B)-1;

  for(i=0; i<=sz(A); ++i){
    while(j >= 0 && suma+sumb-B[j] >= m)
      sumb -= B[j--];

    if(sumb+suma >= m) ans = min(ans, (ll)(j+1)*2+i);
    if(i < sz(A)) suma += A[i];
  }
  cout << ans << endl;
}


int main(){
  tcs(solve)
  return 0;
}
