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.io.*;
import java.util.*;
 
public class Main {
	static class FastReader
	{
	BufferedReader br;
	StringTokenizer st;
 
	public FastReader()
	{
	br = new BufferedReader(new
	InputStreamReader(System.in));
	}
 
	String next()
	{
	while (st == null || !st.hasMoreElements())
	{
	try
	{
	st = new StringTokenizer(br.readLine());
	}
	catch (IOException e)
	{
	e.printStackTrace();
	}
	}
	return st.nextToken();
	}
 
	int nextInt()
	{
	return Integer.parseInt(next());
	}
 
	long nextLong()
	{
	return Long.parseLong(next());
	}
 
	double nextDouble()
	{
	return Double.parseDouble(next());
	}
 
	String nextLine()
	{
	String str = "";
	try
	{
	str = br.readLine();
	}
	catch (IOException e)
	{
	e.printStackTrace();
	}
	return str;
	}
	}
	static long m = 8008808808808813l;
	static long mod(long x) {
		return ((x%m + m)%m);
	}
	static long add(long a,long b) {
		return mod(mod(a)+mod(b));
	}
	static long mul(long a,long b) {
		return mod(mod(a) * mod(b));
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int t = 1;
    	t = sc.nextInt();
    	while(t-->0) {
    		int n = sc.nextInt();
    		int m = sc.nextInt();
    		int a[] = new int[n];
    		int b[] = new int[n];
    		for(int i=0;i<n;i++) a[i] = sc.nextInt();
    		List<Integer> reg = new ArrayList<>();
    		List<Integer> imp = new ArrayList<>();
    		for(int i=0;i<n;i++) {
    			b[i] = sc.nextInt();
    			if(b[i] == 1) reg.add(a[i]);
    			else imp.add(a[i]);
    		}
    		Collections.sort(reg, Collections.reverseOrder());
    		Collections.sort(imp, Collections.reverseOrder());
    		for(int i=1;i<reg.size();i++) {
    			reg.set(i, reg.get(i)+reg.get(i-1));
    		}
    		for(int i=1;i<imp.size();i++) {
    			imp.set(i, imp.get(i)+imp.get(i-1));
    		}	
    		int ans = Integer.MAX_VALUE;
    		for(int i=0;i<reg.size();i++) {
    			int sum = reg.get(i);
    			int res = (i+1);
    			if(sum>=m) {
    				ans = Math.min(ans, res);
    				continue;
    			}
    			int k = lb(imp,m - sum);
    			if(k == -1) continue;
    			res += 2*(k+1);
    			ans = Math.min(ans, res);
    		}
    		for(int i=0;i<imp.size();i++) {
    			int sum = imp.get(i);
    			int res = 2*(i+1);
    			if(sum>=m) {
    				ans = Math.min(ans, res);
    				continue;
    			}
    			int k = lb(reg,m - sum);
    			if(k == -1) continue;
    			res += (k+1);
    			ans = Math.min(ans, res);
    		}
    		if(ans == Integer.MAX_VALUE) ans = -1;
     		System.out.println(ans);
    	}
	}
	private static int lb(List<Integer> reg, int s) {
		int l = 0,h = reg.size()-1;
		if(h == -1) return -1;
		while(l<h) {
			int mid = (l+h)/2;
			if(reg.get(mid)>=s) h = mid;
			else l = mid+1;
		}
		if(reg.get(h)>=s) return h;
		return -1;
	}
//	private static long lb(ArrayList<Long> list, long l) {
//		int lo = 0,h = list.size()-1;
//		int ans = -1;
//		while(lo<=h) {
//			int mid = lo+(h-lo)/2;
//			if(list.get(mid)<=l) {
//				if(mid>0 && list.get(mid-1)==l) h = mid - 1;
//				else {
//					lo = mid+1;
//					ans = mid;
//				}
//			}
//			else {
//				h = mid-1;
//			}
//		}
//		return ans+1;
//	}
	private static int ub(List<Long> list, long l) {
		int lo = 0,h = list.size()-1;
		int ans = -1;
		while(lo<=h) {
			int mid = lo+(h-lo)/2;
			if(list.get(mid)<=l) {
				lo = mid+1;
				ans = mid;
			}
			else {
				
				h = mid-1;
			}
		}
		
		return ans+1;
	}
	private static int check(int i, int x) {
		int cnt = 0;
		while(i%x==0 && i>0) {
			i = i/x;
			cnt++;
		}
		return cnt;
	}
	static String reverse(String x) {
		StringBuilder input1 = new StringBuilder();
		
        input1.append(x);
        
        input1 = input1.reverse();
        
        return input1.toString();
	}
	private static long lsbt(long val) {
		long msk = val&(val-1);
		return (int) (Math.log(val^msk)/Math.log(2));
	}
	private static int sqrt(long x) {
		long l = 1,h = x;
		int ans = 0;
		while(l<=h) {
			long mid = (l+(h-l)/2);
			if(mid>x/mid) h = mid-1;
			else {
				ans = (int) mid;
				l = mid+1;
			}
		}
		return ans;
	}
}
class pair implements Comparable<pair>{
	long a;
	long b;
	pair(long a,long b){
		this.a = a;
		this.b = b;
	}
	@Override
	public int compareTo(pair o) {
		// TODO Auto-generated method stub
		return (int) (o.b - this.b);
	}
}
class spair{
	pair p;
	int id;
	spair(pair p,int id){
		this.p = p;
		this.id = id;
	}
}