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.
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>  using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll           long long
#define rep(i,j,n)   for(int i=j;i<n;i++)
#define scn(a)       scanf("%d",&a)
#define scns(a,b)    scanf("%d %d",&a,&b)
#define print(a)     printf("%d\n",a)
#define vec          vector<int>
#define pb           emplace_back    
#define pairs        pair<int,int>
#define f            first
#define s            second
#define all(v)       v.begin(),v.end()
#define mem(a,b)     memset(a,b,sizeof(a))
#define inf          (int)2e9+7
const int mod = 1e9+7;
const int N = 5e5+5;

template <class F>
struct y_combinator 
{
    F f;

    template <class... Args>
    decltype(auto) operator()(Args&&... args) const 
    {
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) 
{
    return {std::forward<F>(f)};
}

int n;

int main()
{
    int test; scn(test);

    while(test--)
    {
        int m; scns(n,m); int a[n], b[n]; ll sum = 0; 

		vec v1[2];

		rep(i,0,n)
		scn(a[i]), sum += a[i];

		rep(i,0,n)
		scn(b[i]), v1[b[i]-1].pb(a[i]);

		if(sum<m)
		{
			print(-1);

			continue;
		}

		rep(i,0,2)
		sort(all(v1[i]), greater<int>());

		int sz1 = (int)v1[0].size(), sz2 = (int)v1[1].size(), i = 0, j = 0; sum = 0;

		// cout<<sz1<<" "<<sz2<<endl;

		int ans = 0;

		while(sum<m && i+1<sz1 && j<sz2)
		{
			if(v1[0][i]+sum >= m)
			{
				ans++, sum += v1[0][i];

				break;
			}

			int tot = v1[0][i]+v1[0][i+1];

			if(tot+sum >= m)
			{
				ans += 2, sum += tot;

				break;
			}

			if(v1[0][i]+v1[1][j]+sum >= m)
			{
				ans += 3, sum += v1[0][i]+v1[1][j];

				break;
			}

			if(tot >= v1[1][j])
			sum += tot, i += 2, ans += 2;
			else
			sum += v1[1][j], j++, ans += 2;
		}
		// cout<<sum<<" "<<i<<" "<<j<<endl;
		if(sum >= m)
		{
			print(ans);

			continue;
		}

		if(i == sz1-1 && sum+v1[0][i] >= m)
		{
			print(ans+1);

			continue;
		}
		// cout<<sum<<" "<<i<<" "<<j<<endl;
		if(j == sz2)
		{
			while(i<sz1 && sum<m)
			{
				sum += v1[0][i], i++, ans++;

				if(sum >= m)
				break;
			}
		}
		else
		{
			while(j<sz2)
			{
				if(i<sz1 && v1[0][i]+sum >= m)
				{
					ans++;

					break;
				}

				if(v1[1][j]+sum >= m)
				{
					ans += 2;

					break;
				}

				if(i<sz1 && v1[0][i]+v1[1][j]+sum >= m)
				{
					ans += 3;

					break;
				}

				if(i<sz1 && v1[0][i]>v1[1][j])
				sum += v1[0][i], ans++, i++;
				else
				sum += v1[1][j], ans += 2, j++;
			}
		}

		print(ans);
    }
}