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>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define ff          first
#define ss          second
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector <int>
#define mii         map <int,int>
#define mxhi        priority_queue<int>
#define mnhi        priority_queue<int,vi,greater<int> >
#define mod         1000000007
#define setbits(x)  __builtin_popcountll(x)
#define zrobits(x)  __builtin_ctzll(x)   //no of zero bits befor the first set bits
#define inf         1e18
#define ps(x,y)     fixed<<setprecision(y)<<x
#define w(x)        int x; cin>>x; while(x--)
#define int         long long
vector<int> pn;
template<typename T>
class graph
{
    map<T,list<T> > l;
public:
    void addedge(T x,T y)
    {

        l[x].push_back(y);
        l[y].push_back(x);
    }
    void dfs_helper(T src,map <T,bool> &visited,int count=0)   // passing bby address is necessary like 1
    {

        cout<<src<<" ";
        visited[src]=true;
        bool ikv=false;
        for(auto x:l[src])
        {

            if(visited[x]==0)
            {  ikv=true;

                dfs_helper(x,visited,count+1);
            }
        }

            
    }

    void dfs(T src)
    {



        map<T,bool> visited;
        for(auto x:l)
        {

            visited[x.first]=false;

        }
        dfs_helper(src,visited);


    }
    void bfs(T src)
    {
        queue <T> q;
        map<T,int> m;
        for(auto x:l)
        {

            m[x.first]=INT_MAX;
        }
        q.push(src);
        m[src]=0;
        while(!q.empty())
        {

            T top=q.front();
            q.pop();
          //  cout<<top<<" ";
            for(auto nbr:l[top])
            {
                if(m[nbr]==INT_MAX)
                {

                    q.push(nbr);
                    m[nbr]=m[top]+1;
                }

            }
        }
                

    }
void print()
    {

        for(auto p:l)
        {

            cout<<p.first<<"-> ";
            for(auto nbr:l.second)
            {

                cout<<nbr<<" ";
            }
            cout<<endl;
        }
    }


};
// void calncr()
// {
//      for(int n = 0 ; n <= 2000 ; ++n){
//         for(int r = 0 ; r <= n ;++r){
//             if(n==r){
//                 C[n][r] = 1; 
//             }
//             else if(r == 0){
//                 C[n][r] = 1 ; 
//             }
//             else if(r == 1){
//                 C[n][r] = n; 
//             }
//             else{
//                 C[n][r] = C[n-1][r] + C[n-1][r-1] ; 
//             }
//          //   if(n<=10 and r <= 10)
//           //  cout << n << " " << r << " " << C[n][r] << "\n" ; 
//         }
//     }
// }
void SieveOfEratosthenes(int n) 
{   bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        
        if (prime[p] == true) 
        { 
         
        for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
         pn.pb(p);
} 
int fp(int a,int n)
{
    int ans=1;
    while(n>0)
    {
        bool lb=n&1;
        if(lb)
            ans=(ans*a);
        a=(a*a);
        n=n>>1;
    }
    return ans;
}
typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update>
        PBDS;
void i_n()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
    #endif
}

void solve()
{
   int m,n;
   cin>>n>>m;
   vector <int> ss;
   vector <int> mh;
   pii arr[n];
   for (int i = 0; i < n; ++i)
   {
       /* code */
    cin>>arr[i].ff;
   }
   for (int i = 0; i < n; ++i)
   {
       /* code */
    cin>>arr[i].ss;
   }
   sort(arr,arr+n);
   int sum=0;
   int id=-1;
   int pts=0;
   for(int i=n-1;i>=0;i--)
   {
    sum+=arr[i].ff;
    pts+=arr[i].ss;
    if(sum>=m)
    {
        id=i;
        break;
    }
   }
   if(id==-1)
   {
    cout<<-1<<endl;
    return;
   }
   multiset <int> mm;
   for(int j=0;j<id;j++)
   { 
    if(arr[j].ss==1)
    mm.insert(arr[j].ff);
   }
   for(int j=id;j<n&&!mm.empty();j++)
   {
    if(arr[j].ss==2)
    { 
       int sum1=sum;
       sum1-=arr[j].ff;
       int dif=m-sum1;
       auto it=mm.lower_bound(dif);
       if(it!=mm.end()){
       int val=*(it);
       if(val>=dif)
       {
        sum-=arr[j].ff;
        pts--;
        sum+=val;
        mm.erase(mm.find(val));
       }
       
}
    }
   }

   cout<<pts<<endl;

}
main()
{
    i_n();
    w(t)
    solve();
    

}
