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.
/*******************************************************************************
 * author  : dante1
 * created : 26/01/2021 10:22
 *******************************************************************************/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
// import java.math.BigInteger;
import java.util.*;

public class d {
    public static void main(String[] args) {
        int T = in.nextInt();
TEST:   while (T-- > 0) {
            int n = in.nextInt();
            long m = in.nextLong();
            int[] a = in.readIntArray(n);
            List<Long> p1 = new ArrayList<>();
            List<Long> p2 = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (in.nextInt() == 1) {
                    p1.add(1l*a[i]);
                } else {
                    p2.add(1l*a[i]);
                }
            }
            Collections.sort(p1, Collections.reverseOrder());
            Collections.sort(p2, Collections.reverseOrder());
            for (int i = 1; i < p1.size(); i++) {
                p1.set(i, p1.get(i) + p1.get(i-1));
            }
            long ans = Long.MAX_VALUE;
            long sum = 0l;
            for (int i = -1; i < p2.size(); i++) {
                if (i >= 0) {
                    sum += p2.get(i);
                }
                if (sum >= m) {
                    ans = Math.min(2*(i+1), ans);
                } else {
                    int j = search(p1, m-sum);
                    if (j < p1.size() && sum + p1.get(j) >= m) {
                        ans = Math.min(2*(i+1) + j+1, ans);
                    }
                }
                //out.println(ans);
            }
            out.println((ans == Long.MAX_VALUE)? -1 : ans);
        }
        out.flush();
        out.close();
    }

    // Change Array type as necessary.
    static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            out.print(arr[i] + " ");
        }
        out.println();
    }

    static int search(List<Long> arr, long target) {
        // ~ [lower_bound] & [upper_bound -> search for 1+target]
        int lo = 0, hi = arr.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (arr.get(mid) >= target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        // Ensure existence for exact matches
        // if (lo == arr.length || arr[lo] != target)
        // {
        //     return -1;
        // }
        return lo;
    }

    static void sort(int[] arr) {
        // Random Shuffle guarantees O(nlogn) WCTC for Quick Sort.
        Random rnd = new Random();
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, rnd.nextInt(i));
        }
        // Dual-Pivot Quicksort Implementation
        Arrays.sort(arr);
    }

    static boolean[] sieve(int n) {
        boolean[] primes = new boolean[n + 1];
        primes[2] = true;
        for (int i = 3; i <= n; i += 2) {
            primes[i] = true;
        }
        for (int p = 3; 1l * p * p <= n; p += 2) {
            if (primes[p]) {
                for (int k = p * p; k <= n; k += p) {
                    primes[k] = false;
                }
            }
        }
        return primes;
    }

    // MLE -> Use BitSet
    static BitSet bitsieve(int n) {
        BitSet primes = new BitSet(n + 1);
        primes.set(2);
        for (int i = 3; i <= n; i += 2) {
            primes.set(i);
        }
        for (int p = 3; 1l * p * p <= n; p += 2) {
            if (primes.get(p)) {
                for (int k = p * p; k <= n; k += p) {
                    primes.set(k, false);
                }
            }
        }
        return primes;
    }

    static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    static void swap(int x, int y) {
        x = x ^ y;
        y = x ^ y;
        x = x ^ y;
    }

    // Precompute before running testcases
    static long[] fact;
    static void factorial(int lim) {
        fact = new long[lim];
        fact[0] = 1;
        for (int i = 1; i < lim; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
    }

    static long modInv(long x) {
        return pow(x, MOD - 2, MOD);
    }

    static long modInv(long x, int MOD) {
        return pow(x, MOD - 2, MOD);
    }

    static long perm(int n, int r) {
        // assert(fact != null);
        if (n < r) {
            return 0;
        }
        return (fact[n] * (modInv(fact[n - r]) % MOD)) % MOD;
    }

    static long comb(int n, int r) {
        // assert(fact != null);
        if (n < r) {
            return 0;
        }
        if (n == r) {
            return 1;
        }
        return (fact[n] * (((fact[r] % MOD) * (fact[n - r] % MOD)) % MOD)) % MOD;
    }

    static long pow(long x, long y) {
        // assert(y >= 0);
        if (x == 0) {
            return 0;
        }
        if (x == 1 || y == 0) {
            return 1;
        }
        long res = 1l;
        while (y > 1) {
            if ((y & 1) == 1) {
                res *= x;
            }
            x *= x;
            y >>= 1;
        }
        return res * x;
    }

    static long pow(long x, long y, int MOD) {
        // assert(y >= 0);
        if (x == 0) {
            return 0;
        }
        if (x == 1 || y == 0) {
            return 1;
        }
        // Use Math.floorMod or (MOD + res)%MOD
        // for handling negative x if necessary.
        x %= MOD;
        long res = 1l;
        while (y > 1) {
            if ((y & 1) == 1) {
                res = (res * x) % MOD;
            }
            x = (x * x) % MOD;
            y >>= 1;
        }
        return (res * x) % MOD;
    }

    // Handle I/O
    static int MOD = (int) (1e9 + 7);
    static FastScanner in = new FastScanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        int[] readIntArray(int size) {
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

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

        long[] readLongArray(int size) {
            long[] arr = new long[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        double[] readDoubleArray(int size) {
            double[] arr = new double[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextDouble();
            }
            return arr;
        }
    }
}
