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>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define mod 1000000007 
#define INF 1000000000000000000
#define mt make_tuple
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define MAXN 1000001 
#define out(x) cout<<x<<endl;
#define scan(x) cin>>x;
using namespace __gnu_pbds; 
using namespace std;
 
 //policy based structure
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, 
			tree_order_statistics_node_update> 
	new_data_set; 
	
 bool sortbysec(const pair<double,int> &a,const pair<double,int> &b) 
{ 
    return (a.second < b.second); 
} 
 
bool sortbysectuple(const tuple<int, int, int>& a,const tuple<int, int, int>& b) 
{ 
    return (get<1>(a) < get<1>(b)); 
} 
 
bool sortbyth(const tuple<ll, ll, ll>& a,const tuple<ll, ll, ll>& b) 
{ 
    return (get<2>(a) < get<2>(b)); 
} 
 
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first);auto hash2 = hash<T2>{}(p.second); return hash1 ^ hash2; 
    } 
};
 
long modpow(long a, long x, long p) {

    long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}

ll solution(ll a,ll b,ll &x,ll &y){
 
  if(b==0){
    x=1;
    y=0;
    return a;
  }
  ll x1,y1;
  ll g=solution(b,a%b,x1,y1);
  x=y1;
  y=x1-y1*(a/b);
  return g;
  // x=x0+k*(b/g) y=y0-k*(a/g) all solutions
}
 
 bool cmp(ll n, pair<ll, ll> const& p)
{
    // For instance...
    return ((p.first < n) && (p.second < n));
}

ll power(ll a, ll b){ 
	ll x = 1, y = a; 
	while (b > 0){ 
		if (b%2){ 
			x = (x*y)%mod; 
		} 
		y = (y*y)%mod; 
		b /= 2; 
	} 
	return x%mod; 
}	 
 
ll modular_inverse(ll n){ 
	return power(n, mod-2); 
} 
 
 ll factorial[1001];
 
ll nCr(ll n, ll k){ 

     if(n<k)
     return 0;
     
     if(k==0)
     return 1;
     
	 return (factorial[n]*((modular_inverse(factorial[k])*modular_inverse(factorial[n-k]))%mod))%mod; 
} 

struct myComp { 
    constexpr bool operator()( 
        pair<int, int> const& a, 
        pair<int, int> const& b) 
        const noexcept 
    { 
        if(a.fi<b.fi)
        return true;
        if(a.fi==b.fi)
        return a.se>b.se;
    
        return false;
    } 
}; 
  
  
int main()  {
  
      ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
      // priority_queue<int, vector<int>, greater<> > Q; // min priority_queue
      //    map<int, int> gquiz2(gquiz1.begin(), gquiz1.end());
      //set <int, greater <int> > s1;         
      // unordered_map<pair<ll, ll>, ll , hash_pair> um,ba; 
     // new_data_set p; 
      // *p.find_by_order(x) *p.order_of_key(x)
      // partial_sum(a,a+n,b) accumulate(a,a+n,sum);
      
        ll t;
        cin>>t;
        //t=1;
        
          string s;
         
       
  	    while(t--) {
         
          ll n,m,i;
          
          cin>>n>>m;
          
          ll x[n],y;
          
          for(i=0;i<n;i++)
          cin>>x[i];
          
          vector<ll>v,v1;
         
          for(i=0;i<n;i++)
          {
              cin>>y;
              if(y==1)
              v.pb(x[i]);
              else
              v1.pb(x[i]);
          }
         
          sort(v.begin(),v.end(),greater<int>());
          sort(v1.begin(),v1.end(),greater<int>());
          
          ll l=0,r=0,ans=0,cnt=0,prev=-1;
          
          
          while(l<v.size() || r<v1.size())
          {
              if(l<v.size() && ans+v[l]>=m)
              {
                  ans+=v[l];
                  cnt++;
                  break;
              }
              else if(l+1<v.size() && r<v1.size())
              {
                  if(v[l]+v[l+1]>=v1[r])
                  {
                      ans+=v[l]+v[l+1];
                      prev=v[l+1];
                      l+=2;
                  }
                  else
                  {
                      ans+=v1[r];
                      r++;
                  }
                  
                  cnt+=2;
              }
              else if(r<v1.size())
              {
                  ans+=v1[r];
                  
                  if(prev!=-1 && ans>=m)
                  {
                      if(ans-prev>=m)
                      {
                        ans-=prev;
                        cnt--;
                      }
                  }
                  
                  cnt+=2;
                  r++;
              }
              else
              break;
             
              if(ans>=m)
              break;
         }
  	        
  	        
  	        if(ans>=m)
  	        cout<<cnt<<endl;
  	        else
  	        cout<<-1<<endl;
  	        
  	    }
      	 return 0;
}
