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.awt.PageAttributes;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class A {
	static int n;
	static int[] a;
	static int[] b;

	static int[][] memo;
	static HashMap<Integer, Integer> hm;

	static int dp(int idxA, int idxB) {
		if (idxA == n || idxB == n)
			return 0;
		if (memo[idxA][idxB] != -1)
			return memo[idxA][idxB];
		int l = dp(idxA + 1, idxB);
		int t = 0;
		int temp = hm.get(a[idxA]);
		if (temp >= idxB)
			t = 1 + dp(idxA + 1, temp + 1);
		return memo[idxA][idxB] = Math.max(l, t);
	}

	static int mod = 1000000007;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		int t = sc.nextInt();
		

		while (t-- > 0) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			ArrayList<Integer> one = new ArrayList<>();
			ArrayList<Integer> two = new ArrayList<>();
			int[] a =new int[n];
			for (int i = 0; i < n; i++) {
				a[i] =sc.nextInt();
			}
			for (int i = 0; i < a.length; i++) {
				int x =sc.nextInt();
				if(x==1) {
					one.add(a[i]);
				}
				else
					two.add(a[i]);
			}
			Collections.sort(one,Collections.reverseOrder());
			Collections.sort(two,Collections.reverseOrder());
			int i = 0 ;
			int j = 0;
			int ans = 0;
			while(m>0) {
				if(i==one.size() && j == two.size()) {
					ans = -1 ;
					break;
				}
				else if(i==one.size()) {
					m-=two.get(j);
					j++;
					ans+=2;
				}
				else if (j == two.size()) {
					m-=one.get(i);
					i++;
					ans++;
				}
				else {
					if(m-one.get(i) <=0) {
						m-=one.get(i);
						i++;
						ans++;
					}
					else if(i== one.size()-1) {
						m-=two.get(j);
						j++;
						ans+=2;
					}
					else {
						if(one.get(i)+one.get(i+1) > two.get(j)) {
							m-=one.get(i);
							i++;
							ans++;
						}
						else {
							m-=two.get(j);
							j++;
							ans+=2;
						}
					}
				}
			}
			pw.println(ans);
		}

		pw.flush();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public int[] intArr(int n) throws IOException {
			int a[] = new int[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public long[] longArr(int n) throws IOException {
			long a[] = new long[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
			}
			return a;
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	static int modinverse(int n, int p) {
		return modPow(n, p - 2, p);
	}

	static int modPow(int a, int e, int mod) // O(log e)
	{
		a %= mod;
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res = (res * a) % mod;
			a = (int) ((a * 1l * a) % mod);
			e >>= 1;
		}
		return (int) res;
	}

	static int far[], value[];

	static final long INF = (long) 1e18; // don't increase, avoid overflow
	static ArrayList<Edge>[] adjList, g;
	static int V;

	/*
	 * 1. Dijkstra's Algorithm for SSSP on weighted graphs
	 */
	static long[][] dijkstra(int S, int T) // O(E log E)
	{
		long[][] dist = new long[4][V];
		for (int i = 0; i < dist.length; i++) {
			Arrays.fill(dist[i], INF);
		}

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		dist[0][S] = 0;
		dist[1][S] = 0;
		dist[2][S] = 0;
		dist[3][S] = 0;
		pq.add(new Edge(S, 0)); // may add more in case of MSSP (Mult-Source)
		while (!pq.isEmpty()) {
//			System.out.println(pq);
			Edge cur = pq.remove();
			if (cur.free && cur.two) {
				if (cur.cost > dist[3][cur.node]) // lazy deletion
					continue;
			} else if (cur.free) {
				if (cur.cost > dist[1][cur.node]) // lazy deletion
					continue;
			} else if (cur.two) {
				if (cur.cost > dist[2][cur.node]) // lazy deletion
					continue;
			} else {
				if (cur.cost > dist[0][cur.node]) // lazy deletion
					continue;
			}
			for (Edge nxt : adjList[cur.node]) {
				if (cur.free && cur.two) {
					if (cur.cost + nxt.cost < dist[3][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[3][nxt.node] = cur.cost + nxt.cost, true, true));
				} else if (cur.free) {
					if (cur.cost + nxt.cost < dist[1][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[1][nxt.node] = cur.cost + nxt.cost, true, false));
					if (cur.cost + nxt.cost * 2 < dist[3][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[3][nxt.node] = cur.cost + nxt.cost * 2, true, true));
				} else if (cur.two) {
					if (cur.cost + nxt.cost < dist[2][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[2][nxt.node] = cur.cost + nxt.cost, false, true));
					if (cur.cost < dist[3][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[3][nxt.node] = cur.cost, true, true));
				} else {
					if (cur.cost + nxt.cost < dist[0][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[0][nxt.node] = cur.cost + nxt.cost, false, false));
					if (cur.cost < dist[1][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[1][nxt.node] = cur.cost, true, false));
					if (cur.cost + nxt.cost * 2 < dist[2][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[2][nxt.node] = cur.cost + nxt.cost * 2, false, true));
					if (cur.cost + nxt.cost < dist[3][nxt.node]) // lazy deletion
						pq.add(new Edge(nxt.node, dist[3][nxt.node] = cur.cost + nxt.cost, true, true));
				}
			}
		}
		return dist;

	}

	static class Edge implements Comparable<Edge> {
		int node;
		long cost;
		boolean free, two;

		Edge(int a, int b) {
			node = a;
			cost = b;
		}

		Edge(int a, long b, boolean f, boolean g) {
			node = a;
			cost = b;
			free = f;
			two = g;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return node + " " + cost + " " + free + " " + two;
		}

		public int compareTo(Edge e) {
			return Long.compare(cost, e.cost);
		}
	}

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

		public pair(int d, int u, int i) {
			x = d;
			y = u;
			idx = i;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			if (o.x == x)
				return o.y - y;
			return o.x - x;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return x + " " + y;
		}

	}
}