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.util.*;
import java.io.*;  
import java.util.Map.Entry;
 
public class Solution{
    public static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
        public String next() {
			while (st == null || !st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) {
				a[i]=nextInt();
			}
			return a;
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
    }
    public static class unionFind{
        public static int[] p;
        public static int find(int u){
            while(p[u]!=u){
                u=p[u];
            }
            return u;
        }
        public static void union(int u,int v){
            int x=find(u);
            int y=find(v);
            p[x]=y;
        }
    }
    static class Point{ 
        double x; 
        double y; 
        public Point(double x, double y){ 
            this.x = x; 
            this.y = y; 
        } 
    }
    public static class SegmentTree{ 
        int st1[];
        int st2[];
        SegmentTree(int arr[], int n){ 
            int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
            int max_size = 2 * (int) Math.pow(2, x) - 1;
            st1 = new int[max_size];
            st2 = new int[max_size];
            constructSTUtil1(arr, 0, n - 1, 0);
            constructSTUtil2(arr, 0, n - 1, 0); 
        }
        int getMid(int s, int e) { 
            return s + (e - s) / 2; 
        }
        int getSumUtil(int ss, int se, int qs, int qe, int si){
            if (qs <= ss && qe >= se){
                return st1[si]; 
            }
            if (se < qs || ss > qe) {
                return 0; 
            }
            int mid = getMid(ss, se); 
            return getSumUtil(ss, mid, qs, qe, 2 * si + 1) + getSumUtil(mid + 1, se, qs, qe, 2 * si + 2); 
        }
        int getMinUtil(int ss, int se, int qs, int qe, int si){
            if (qs <= ss && qe >= se){
                return st2[si]; 
            }
            if (se < qs || ss > qe) {
                return Integer.MAX_VALUE; 
            }
            int mid = getMid(ss, se); 
            return Math.min(getMinUtil(ss, mid, qs, qe, 2 * si + 1),getMinUtil(mid + 1, se, qs, qe, 2 * si + 2)); 
        }
        int getMaxUtil(int ss, int se, int qs, int qe, int si){
            if (qs <= ss && qe >= se){
                return st1[si]; 
            }
            if (se < qs || ss > qe) {
                return Integer.MIN_VALUE; 
            }
            int mid = getMid(ss, se); 
            return Math.max(getMaxUtil(ss, mid, qs, qe, 2 * si + 1),getMaxUtil(mid + 1, se, qs, qe, 2 * si + 2)); 
        }
        void updateValueUtil(int ss, int se, int i, int diff, int si){ 
            if (i < ss || i > se){
                return; 
            }
            st1[si] = st1[si] + diff; 
            if (se != ss) { 
                int mid = getMid(ss, se); 
                updateValueUtil(ss, mid, i, diff, 2 * si + 1); 
                updateValueUtil(mid + 1, se, i, diff, 2 * si + 2); 
            } 
        }
        void updateValue(int arr[], int n, int i, int new_val){
            if (i < 0 || i > n - 1) {
                return; 
            }
            int diff = new_val - arr[i]; 
            arr[i] = new_val; 
            updateValueUtil(0, n - 1, i, diff, 0); 
        }
        int getSum(int n, int qs, int qe){
            if (qs < 0 || qe > n - 1 || qs > qe) {
                return -1; 
            } 
            return getSumUtil(0, n - 1, qs, qe, 0); 
        }
        int getMin(int n, int qs, int qe){
            if (qs < 0 || qe > n - 1 || qs > qe) {
                return Integer.MIN_VALUE; 
            } 
            return getMinUtil(0, n - 1, qs, qe, 0); 
        }
        int getMax(int n, int qs, int qe){
            if (qs < 0 || qe > n - 1 || qs > qe) {
                return Integer.MAX_VALUE; 
            } 
            return getMaxUtil(0, n - 1, qs, qe, 0); 
        }
        int constructSTUtil1(int arr[], int ss, int se, int si){
            if (ss == se) { 
                st1[si] = arr[ss]; 
                return arr[ss]; 
            }
            int mid = getMid(ss, se); 
            st1[si] = Math.max(constructSTUtil1(arr, ss, mid, si * 2 + 1),constructSTUtil1(arr, mid + 1, se, si * 2 + 2)); 
            return st1[si]; 
        }
        int constructSTUtil2(int arr[], int ss, int se, int si){
            if (ss == se) { 
                st2[si] = arr[ss]; 
                return arr[ss]; 
            }
            int mid = getMid(ss, se); 
            st2[si] = Math.min(constructSTUtil2(arr, ss, mid, si * 2 + 1),constructSTUtil2(arr, mid + 1, se, si * 2 + 2)); 
            return st2[si]; 
        } 
    }
    public static double area(Point A, Point B, Point C){ 
        double area = (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / (double)2; 
        return Math.abs(area);
    }
    public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<>();
		for(int i:array){
			copy.add(i);
		}
		Collections.sort(copy);
		for(int i=0;i<array.length;i++){
			array[i]=copy.get(i);
		}
    }
    static long[] fact(){
        long[] fac = new long[1000000];
        fac[0] = (long)1;
        for (int i = 1; i < (int)fac.length; i++){
            fac[i] = (fac[i - 1] * i);
        }
        return fac;
    }
    public static long nCr(long n, long r,long p,long[] fac){
        if (n<r) 
              return (long)0;
        if (r == 0)
            return (long)1;
        return (fac[(int)n] * modInverse(fac[(int)r], p)% p * modInverse(fac[(int)(n - r)], p)% p)% p;
    }
    public static long modInverse(long n, long p){
        return power(n, p - 2, p);
    }
    static long power(long x, long y, long p){
        long res = 1;
        x = x % p;
        while (y > 0) {
            if (y % 2 == 1)
                res = (res * x) % p;
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
    public static int upp(int[] arr,int v){
        int low=0;
        int high=arr.length-1;
        int ans=-1;
        while(low<=high){
            int m=(low+high)/2;
            if(arr[m]<v){
                ans=m;
                low=m+1;
            }else{
                high=m-1;
            }
        }
        return ans;
    }
    public static int low(int[] arr,int v){
        int low=0;
        int high=arr.length-1;
        int ans=-1;
        while(low<=high){
            int m=(low+high)/2;
            if(arr[m]>v){
                ans=m;
                high=m-1;
            }else{
                low=m+1;
            }
        }
        return ans;
    }
    public static class Comp implements Comparator<pair>{
        public int compare(pair a,pair b){
            if(a.y!=b.y){
                return a.y-b.y;
            }else{
                return b.x-a.x;
            }
        }
    }
    public static int gcd(int a,int b){
        if (b == 0) 
        return a; 
        return gcd(b, a % b);
    }
    public static int lcm(int a,int b){
        int x=Math.max(a,b);
        int y=Math.min(a,b);
        long ans=x;
        while(ans%y!=0){
            ans+=x;
        }
        if(ans>Integer.MAX_VALUE){
            return -1;
        }
        return (int)ans;
    }
    public static class pair{
        int x;
        int y;
        public pair(int a,int b){
            x=a;
            y=b;
        }
    }
    static boolean isPowerOfTwo(long n)
{
    if(n==0)
    return false;
 
return (long)(Math.ceil((Math.log(n) / Math.log(2)))) == 
       (long)(Math.floor(((Math.log(n) / Math.log(2)))));
}
    public static int ans;
    public static void main(String[] args) throws IOException{
        FastScanner fs=new FastScanner();
		int t=1;
		t=fs.nextInt();
		long mod=1000000007;
// 		long[] fact=fact();
		PrintWriter out=new PrintWriter(System.out);
		while(t-->0){
		    int n=fs.nextInt();
		    int m=fs.nextInt();
		    int[] a=fs.readArray(n);
		    int[] b=fs.readArray(n);
		    pair[] arr=new pair[n];
		    for(int i=0;i<n;i++){
		        arr[i]=new pair(a[i],b[i]);
		    }
		    Arrays.sort(arr,new Comp());
		  //  for(int i=0;i<n;i++){
		  //      System.out.println(arr[i].x+" "+arr[i].y);
		  //  }
		    long sum=0;
		    int in=0;
		    long count=0;
		    ArrayList<pair> list=new ArrayList<>();
		    while(in<n && sum<(long)m){
		        sum+=(long)arr[in].x;
		        list.add(arr[in]);
		        count+=(long)arr[in].y;
		        in++;
		    }
		    if(sum<(long)m){
		        System.out.println("-1");
		        continue;
		    }
		    if(list.get(list.size()-1).y==1){
		        System.out.println(list.size());
		        continue;
		    }
		  //  System.out.println(count);
		    long last=sum-(long)m;
		    sum=0;
		    for(int i=0;i<list.size();i++){
		        if(list.get(i).y==2){
		            break;
		        }
		        if((long)list.get(i).x<=last){
		            last-=(long)list.get(i).x;
		            count--;
		        }
		    }
		    System.out.println(count);
		}
        out.close();
    }
}