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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024 * 2);

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {
            // C
//            int[] v = readArrayLine(br.readLine(), 3);
//            int a = v[0];
//            int b = v[1];
//            int k = v[2];
//
//            int[] aa = readArrayLine(br.readLine(), k);
//            int[] bb = readArrayLine(br.readLine(), k);
//
//            int[] boysPairs = new int[a + 1];
//            int[] girlsPairs = new int[b + 1];
//            for (int i = 0; i < k ; i ++) {
//                boysPairs[aa[i]] ++;
//                girlsPairs[bb[i]] ++;
//            }
//
//            long sol = 0;
//            for (int i = 0; i < k ; i++) {
//                sol += k - boysPairs[aa[i]] - girlsPairs[bb[i]] + 1;
//            }
//            sb.append(sol / 2).append('\n');

            sb.append(d(br)).append('\n');


//            sb.append(e(br)).append('\n');
        }

        System.out.println(sb.toString());
    }

    public static long d(BufferedReader br) throws IOException {
            int[] v = readArrayLine(br.readLine(), 2);
            int n = v[0];
            int m = v[1];
            int[] memory = readArrayLine(br.readLine(), n);
            int[] prio = readArrayLine(br.readLine(), n);

            long sum = 0;
            for (int mem : memory) {
                sum += mem;
            }

            if (sum < m) {
                return -1;
            }

            List<Integer> ones = new ArrayList<>();
            List<Integer> twos = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                if (prio[i] == 1) {
                    ones.add(memory[i]);
                } else {
                    twos.add(memory[i]);
                }
            }

            ones.sort((a1, a2) -> a2 - a1);
            twos.sort((a1, a2) -> a2 - a1);

            int x = 0, i = 0, j = 0;
            int cost = 0;
            while (i < ones.size() && j < twos.size() && x < m) {
                // check add just one goes over
                if (x + ones.get(i) >= m) {
                    x += ones.get(i);
                    i++;
                    cost++;
                    break;
                }
                int v1 = ones.get(i) + (i < ones.size() - 1 ? ones.get(i + 1) : 0);
                int v2 = twos.get(j);
                if (v1 < v2) {
                    x += v2;
                    j++;
                    cost += 2;
                } else {
//                    x += v1;
//                    i += 2;
//                    cost += 2;
                    x += ones.get(i);
                    i++;
                    cost ++;
                }
            }

            while (i < ones.size() && x < m) {
                x += ones.get(i++);
                cost++;
            }

            while (j < twos.size() && x < m) {
                x += twos.get(j++);
                cost += 2;
            }

            i--;
            while (x >= m && i >= 0 && x - ones.get(i) >= m) {
                x -= ones.get(i);
                i --;
                cost --;
            }

            return cost;
    }

    public static long e(BufferedReader br) throws IOException {
        buildFact();
        int[] v= readArrayLine(br.readLine(), 2);
        int n = v[0];
        int k = v[1];
        v = readArrayLine(br.readLine(), n);
        Arrays.sort(v);

        int max = 0;
        int pos = n - 1;
        int remaining = k;
        while (remaining > 0) {
            max += v[pos--];
            remaining --;
        }

        TreeMap<Integer, Integer> map = new TreeMap<>((a1, a2) -> a2 - a1);
        for (int x : v) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        long result = 1;
        for (int x : map.keySet()) {
            Integer occ = map.get(x);
            int totalValue = x * occ;
            if (totalValue > max) {
                result = combInPlace(occ, max/x);
                break;
            } else {
                max -= totalValue;
            }
        }
        return result;
    }

    public static int[] readArrayLine(String line, int n) {
        return readArrayLine(line, n, null, 0);
    }

    private static int[] readArrayLine(String line, int n, int array[], int pos) {
        int[] ret = array == null ? new int[n] : array;
        int start = 0;
        int end = line.indexOf(' ', start);
        for (int i = pos; i < pos + n; i++) {
            if (end > 0)
                ret[i] = Integer.parseInt(line.substring(start, end));
            else
                ret[i] = Integer.parseInt(line.substring(start));
            start = end + 1;
            end = line.indexOf(' ', start);
        }
        return ret;
    }

    private static int MAXN = 1001;
    private static long[] fact = new long[MAXN];
    private static long[] factInverse = new long[MAXN];
    private static boolean factBuilt = false;

    private static void buildFact() {
        if (factBuilt) {
            return;
        }
        fact[0] = 1;
        factInverse[0] = 1;
        for (int i = 1; i < fact.length; i++) {
            fact[i] = (fact[i - 1] * (long) i) % MOD;
            factInverse[i] = inv(fact[i]);
        }
        factBuilt = true;
    }

    private static long inv(long k) {
        return modPow(k, MOD - 2, MOD);
    }

    public static long modPow(long base, int exp, int mod) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
                if (result > mod) {
                    result %= mod;
                }
            }
            exp >>= 1;
            base *= base;
            if (base >= mod) {
                base %= mod;
            }
        }
        return result;
    }

    private static int MOD = 1_000_000_007;

    private static long combInPlace(int n, int k) {
        if (n < k) {
            return 0;
        }
        return (((fact[n] * factInverse[k]) % MOD) * factInverse[n - k]) % MOD;
    }
}


