from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from math import inf, sqrt, ceil, log2
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from typing import List
from bisect import bisect_left, bisect_right
import sys
import string
input=lambda:sys.stdin.readline().strip('\n')
mis=lambda:map(int,input().split())
ii=lambda:int(input())
T = ii()
for _ in range(T):
N, M = mis()
A = list(mis())
C = [0] * 61
sum = 0
for a in A:
C[int(log2(a))] += 1
sum += a
binn = format(N, 'b')[::-1]
ans = 0
if N > sum:
print(-1)
continue
for i in range(len(binn)):
if binn[i] == '0':
pass
elif C[i] > 0:
C[i] -= 1
else:
j = i + 1
while C[j] == 0:
j += 1
C[j] -= 1
C[j-1] += 1
j -= 1
ans += 1
while j > i:
ans += 1
C[j-1] += 1
j -= 1
C[i+1] += C[i]//2
print(ans)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int cnt[65];
void solve(int tcId) {
int n, m;
cin >> n >> m;
for (int i = 0; i < 64; i++)
cnt[i] = 0;
for (int i = 0; i < m; i++) {
int v;
cin >> v;
int pow = 0;
while (v > 1) {
v /= 2;
pow++;
}
cnt[pow]++;
}
int ans = 0;
for (int bit = 0; bit < 64; bit++) {
if (n & ((int)1 << bit)) {
if (cnt[bit] > 0) {
cnt[bit]--;
} else {
// need to divide
bool ok = false;
int fst = bit + 1;
for (; fst < 64; fst++) {
if (cnt[fst] > 0) {
ok = true;
break;
}
}
if (!ok) {
cout << "-1\n";
return;
}
cnt[fst]--;
while (fst > bit) {
ans++;
fst--;
cnt[fst]++;
}
}
}
// merge
int nxt = cnt[bit] / 2;
cnt[bit + 1] += nxt;
cnt[bit] %= 2;
}
cout << ans << '\n';
}
signed main() {
bool multi = true;
if (!multi) {
solve(42);
} else {
int t;
cin >> t;
while (t--)
solve(t);
}
}1633C - Kill the Monster | 1611A - Make Even |
1030B - Vasya and Cornfield | 1631A - Min Max Swap |
1296B - Food Buying | 133A - HQ9+ |
1650D - Twist the Permutation | 1209A - Paint the Numbers |
1234A - Equalize Prices Again | 1613A - Long Comparison |
1624B - Make AP | 660B - Seating On Bus |
405A - Gravity Flip | 499B - Lecture |
709A - Juicer | 1358C - Celex Update |
1466B - Last minute enhancements | 450B - Jzzhu and Sequences |
1582C - Grandma Capa Knits a Scarf | 492A - Vanya and Cubes |
217A - Ice Skating | 270A - Fancy Fence |
181A - Series of Crimes | 1638A - Reverse |
1654C - Alice and the Cake | 369A - Valera and Plates |
1626A - Equidistant Letters | 977D - Divide by three multiply by two |
1654B - Prefix Removals | 1654A - Maximum Cake Tastiness |