Fill The Bag CodeForces - 1303D（二進制+位運算）

You have a bag of size nn. Also you have mm boxes. The size of ii-th box is aiai, where each aiai is an integer non-negative power of two.

You can divide boxes into two parts of equal size. Your goal is to fill the bag completely.

For example, if n=10n=10 and a=[1,1,32]a=[1,1,32] then you have to divide the box of size 3232 into two parts of size 1616, and then divide the box of size 1616. So you can fill the bag with boxes of size 11, 11 and 88.

Calculate the minimum number of divisions required to fill the bag of size nn.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains two integers nn and mm (1≤n≤1018,1≤m≤1051≤n≤1018,1≤m≤105) — the size of bag and the number of boxes, respectively.

The second line of each test case contains mm integers a1,a2,…,ama1,a2,…,am (1≤ai≤1091≤ai≤109) — the sizes of boxes. It is guaranteed that each aiai is a power of two.

It is also guaranteed that sum of all mm over all test cases does not exceed 105105.

Output

For each test case print one integer — the minimum number of divisions required to fill the bag of size nn (or −1−1, if it is impossible).

Example

Input

3

10 3

1 32 1

23 4

16 1 4 1

20 5

2 1 16 1 8

Output

2

-1

思路：這種二的幂次的題目，轉化成二進制和位運算的就肯定沒錯了。我們把這m個數，在每一位的有多少個數是1計算出來，然後把n在哪一位上是1也給計算出來。我們從低到高周遊，如果這一位應該有數字但實際沒有的話，就往高位去借。具體看代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxx=1e5+100;
ll a[maxx],b[70];
int xx[70],yy[70];
ll n;int m;

inline void init()
{
	for(int i=0;i<=60;i++) b[i]=(ll)pow(2,i);//1e18，60位就足夠了
}
int main()
{
	init();
	int t;
	scanf("%d",&t);
	while(t--)
	{
		cin>>n>>m;
		ll sum=0;
		for(int i=1;i<=m;i++) cin>>a[i],sum+=a[i];
		if(sum<n) cout<<-1<<endl;
		else if(sum==n) cout<<0<<endl;
		else
		{
			memset(xx,0,sizeof(xx));
			memset(yy,0,sizeof(yy));
			for(int i=60;i>=0;i--) if((n&(ll)b[i])) xx[i]=1;
			for(int i=60;i>=0;i--)
			{
				for(int j=1;j<=m;j++) if((a[j]&(ll)b[i])) yy[i]++;
			}
			int ans=0;
			for(int i=0;i<=60;i++)
			{
				if(xx[i]&&yy[i]>0) yy[i+1]+=((yy[i]-1)>>1);//這一位用完之後，剩下的盡可能的擴充到下一位。
				else if(xx[i]&&yy[i]==0)
				{
					for(int j=i+1;j<=60;j++)
					{
						if(yy[j]>0)
						{
							yy[j]-=1;
							ans++;
							for(int k=j-1;k>i;k--)
							{
								yy[k]+=1;//對于[i+1,j-1]的位數來說，隻增加了一個，剩下的那一個分裂為下一位了。
								ans++;
							}
							yy[i]+=2;//第i位增加兩個。
							break; 
						}
					}
					if(yy[i]>0) yy[i+1]+=((yy[i]-1)>>1);//盡可能的留給下一位
				}
				else if(xx[i]==0&&yy[i]>0) yy[i+1]+=(yy[i]>>1);//盡可能的留給下一位
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}
           

努力加油a啊，(o)/~