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.
// â��Experience is the name everyone gives to their mistakes.â�� â�� Oscar Wilde
// Take care of mod becoming -ve

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fro(i, s, e) for (auto i = s; i <= e; ++i)
#define int long long
#define ld long double
#define fr(i, n) for (int i = 0; i < n; i++)
#define ff first
#define ss second
#define mp make_pair
#define vi std::vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define setbits(x) __builtin_popcountll(x)
#define zrbits(x) __builtin_ctzll(x)
#define tc    \
    int t;    \
    cin >> t; \
    while (t--)
#define FILE                          \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout)
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define ps(x, y) fixed << setprecision(y) << x
#define endl "\n"
#define rev(i, e, s) for (auto i = e; i >= s; --i)
#define mod 1000000007
#define min_pq priority_queue<int, std::vector<int>, greater<int>>
#define printclock cerr << "Time : " << 1000 * (ld)clock() / (ld)CLOCKS_PER_SEC << "ms\n";
using namespace std;
const int N = 1e5 + 5;
const int inf = 1000000000000000000;
#define fit(s, x) memset(s, x, sizeof(s));
#define out(x) cout << x << "\n"
#define deb(x) cout << #x <<": "<< x << "\n"
#define fr1(i, n) for (int i = 1; i <= n; i++)
#define pi 3.14159265358979323846264338327950
typedef tree<int, null_type, less<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        PBDS;
#define debug(...) cerr<<" ["<<#__VA_ARGS__": "<<(__VA_ARGS__)<<"] "
// Use __gcd(a,b) for gcd
// find(all(x),key) to get the iterator and its index is obtained by find(all(x),key)-x.begin()
// find_if(iterator_first,iterator_last,unary function) returns first iterator if any element corresponding to unary function exists and if no such element is found it retrurns the last iterator
/*For example:
find_if(all(x),isodd) for x being a vector{10,25,40,55}; *it returns 25*/
/*search(all(v1),all(v2),pred) searches for all the elements of v2 present in v1 based on pred function the iterator correspond
to the first element of sequence if it exists and if not then th elast iterator is obtained.*/
//use substr(size_t pos,size_t len) for the substrings
// iota(forward itr,backwrd itr,val) can be used for consecutive numbers
//use emplace_back in vector
int power(int a, int b, int m = mod)
{
  long long ans = 1;
  while (b > 0)
  {
    if (b & 1LL)
    {
      ans = (ans * a) % m;
    }
    a = (a * a) % m;
    b = (b >> 1LL);
  }
  return ans;
}

struct comp
{
  template<typename T>
  //sorting based on second
  bool operator()(const T&l,const T&r)const{
    if(l.second!=r.second){
      return l.second<r.second;
    }
    return l.first<r.first;
  }
  
};
int modInv(int a, int m = mod) {
  return power(a, m - 2, m); //m is prime
}

int dx[8] = {0, 1, 0, -1, -1, -1, 1, 1} ;
int dy[8] = {1, 0, -1, 0, -1, 1, 1, -1} ;
int mx=1e6;
bool cmp(pii a,pii b){
  if(a.ff==b.ff){
    return a.ss<b.ss;
  }
  return a.ff>b.ff;
}

inline void solve() {
  int n,m;
  cin>>n>>m;
  std::vector<int> a(n);
  fr(i,n){
    cin>>a[i];
  }
  std::vector<int> b(n);
  fr(i,n)cin>>b[i];
  std::vector<pii> c(n);
  fr(i,n){
    c[i]={a[i],b[i]};
  }
  int total=0;
  fr(i,n){
    total+=a[i];
  }
  if(total<m){
    out(-1);
    return;
  }
  sort(all(c),cmp);
  std::vector<pii> sum(n);
  fr(i,n){
    if(i==0){
      sum[i].ff=c[0].ff;
      sum[i].ss=c[0].ss;
    }else{
      sum[i].ff=sum[i-1].ff+c[i].ff;
      sum[i].ss=sum[i-1].ss+c[i].ss;
    }
  }
  int ans=mx;
  int slow_pointer=0,fast_pointer=1;
  int cur=c[0].ff;
  while(slow_pointer<n){
    while(fast_pointer<n and cur<m){
      cur+=c[fast_pointer].ff;
      fast_pointer++;
    }
    int end=(slow_pointer==0?0:sum[slow_pointer-1].ss);
    if(fast_pointer==n){
      if(cur<m){
        break;
      }
      else{
        ans=min(ans,sum[n-1].ss-end);
      }
    }
    else{
      ans=min(ans,sum[fast_pointer-1].ss-end);
    }
    cur-=c[slow_pointer].ff;
    slow_pointer++;
  }
  out(ans);
} 

int32_t main()
{ 
  fio;
#ifndef ONLINE_JUDGE
  FILE;
#endif
  
  tc{
    solve();
  }
  // solve();
  printclock;
  return 0;
}