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.
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Main {


    static class pair implements Comparable<pair> {
        int x;
        long y;

        public pair(int u, long  v) {
            this.x = u;
            this.y = v;
        }

        @Override
        public int compareTo(pair o) {
            if(x==o.x) {
                if(y>o.y)
                    return -1;
                if(y<o.y)
                    return 1;
                return 0;
            }
            if(x<o.x)
                return -1;
            return 1;
        }
    }

    static double dis(pair a, pair b) {
        return Math.sqrt(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));
    }

    static long c;
    static long d;
    static long e;
    static long mod=1000000007;
    static void extendedEuclid(long a, long b) {
        if (b == 0) {
            c = 1;
            d = 0;
            e = a;
            return;
        }
        extendedEuclid(b, a % b);
        long x1 = d;
        long y1 = c%mod - ((a / b) * d)%mod;
        c = x1;
        c=c%mod;
        d = y1;
        if(d<0)
            d+=mod;
    }
    static int[]rank;
    static int[]p;
    static int sets;
    static int findSet(int i){
        return (p[i]==i)?i:(p[i]=findSet(p[i]));
    }
    static boolean isSameSet(int i,int j){
        return findSet(i)==findSet(j);
    }
    static void unionSet(int i,int j){
        if(!isSameSet(i,j)){
            sets--;
            int x=findSet(i);
            int y=findSet(j);
            if(rank[x]>rank[y])
                p[y]=x;
            else {
                p[x]=y;
                if(rank[x]==rank[y])
                    rank[y]++;
            }
        }
    }
    static class SegmentTree { // 1-based DS, OOP

        int N; // the number of elements in the array as a power of 2 (i.e. after padding)
        long[] array, sTree, lazy;

        SegmentTree(long[] in) {
            array = in;
            N = in.length - 1;
            sTree = new long[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
            lazy = new long[N << 1];
            build(1, 1, N);
        }

        void build(int node, int b, int e) // O(n)
        {
            if (b == e)
                sTree[node] = array[b];
            else {
                int mid = b + e >> 1;
                build(node << 1, b, mid);
                build(node << 1 | 1, mid + 1, e);
                sTree[node] = Math.min(sTree[node << 1] , sTree[node << 1 | 1]);
            }
        }


        long query(int i, int j) {
            return query(1, 1, N, i, j);
        }

        long query(int node, int b, int e, int i, int j) // O(log n)
        {
            if (i > e || j < b)
                return Long.MAX_VALUE;
            if (b >= i && e <= j)
                return sTree[node];
            int mid = b + e >> 1;
            long q1 = query(node << 1, b, mid, i, j);
            long q2 = query(node << 1 | 1, mid + 1, e, i, j);
            return Math.min(q1 , q2);

        }
    }

    static int minIdx(long val,int idx,SegmentTree sg) {

        int lo=idx+1;
        int hi=sg.N;
        int ans=-1;
        while(lo<=hi) {
            int mid=(lo+hi)>>1;
            long x=sg.query(idx+1, mid);
            if(x<=val) {
                ans=mid-1;
                hi=mid-1;
            }
            else {
                lo=mid+1;
            }
        }
        return ans;
    }
    static long[]mem;
    static pair[]in;
    static int [][]vis;
    static long max;
    static int[]next;
    static long[]a;
    static long  dp(int i){
        if(i<0||i>=mem.length)
            return -1;
        if(mem[i]!=-1)
            return mem[i];
        long x=dp(next[i]);

        if(x==-1)
            return mem[i]=a[i];

        return mem[i]=gcd(a[i],x);

    }
    static long gcd(long a,long b){
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
//    static int firstLessThan(int i,long v){
//        return 0;
//    }



    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new FileReader("name.in"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter out = new PrintWriter(System.out);

         int T=Integer.parseInt(br.readLine());
         while(T-->0){
             st=new StringTokenizer(br.readLine());
             int n=Integer.parseInt(st.nextToken());
             long m=Long.parseLong(st.nextToken());
             st=new StringTokenizer(br.readLine());
             StringTokenizer st2=new StringTokenizer(br.readLine());
             pair[]arr=new pair[n];
             int amount1=0;
             int amount2=0;
             for (int i = 0; i <n ; i++) {
                 //pair(b,a)
                 arr[i]=new pair(Integer.parseInt(st2.nextToken()),Long.parseLong(st.nextToken()));
                 if(arr[i].x==1)
                     amount1++;
                 else amount2++;
             }
             Arrays.sort(arr);
             long []result=new long[2*n +1];
             int [] taken1=new int[result.length];
             int [] taken2=new int[result.length];
             int beg=1;
             int ans=-1;
             if(arr[0].x==2)
                 beg=2;
             for (int i = beg; i < result.length ; i++) {
                 long max1=-1;
                 long max2=-1;

                 if(taken1[i-1]<amount1)
                     max1=result[i-1]+arr[taken1[i-1]].y;
                 if(taken2[i-1]<amount2&&i>=2)
                     max2=result[i-2]+arr[amount1+taken2[i-1]].y;
                 if(max1>max2){
                     taken1[i]=taken1[i-1]+1;
                     taken2[i]=taken2[i-1];
                     result[i]=max1;
                 }
                 if(max2>max1){
                     taken1[i]=taken1[i-2];
                     taken2[i]=taken2[i-2]+1;
                     result[i]=max2;
                 }
                 if(max2==max1&&max1!=-1){
                     taken1[i]=taken1[i-2];
                     taken2[i]=taken2[i-2]+1;
                     result[i]=max2;
                 }
                 if(max2==max1&&max1==-1) {
                     result[i] = result[i - 1];
                     taken1[i]=taken1[i-1];
                     taken2[i]=taken2[i-1];
                 }
                 if(result[i]>=m){
                     ans=i;
                     break;
                 }

             }
            out.println(ans);

         }






        out.flush();
        out.close();

    }

}