D. Fill The Bag
bitmasks; greedy
You have a bag of size \(n\). Also you have \(m\) boxes. The size of \(i\)-th box is \(a_i\), where each \(a_i\) 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 = 10\) and \(a = [1, 1, 32]\) then you have to divide the box of size \(32\) into two parts of size \(16\), and then divide the box of size \(16\). So you can fill the bag with boxes of size \(1\), \(1\) and \(8\).Calculate the minimum number of divisions required to fill the bag of size \(n\).
The first line contains one integer \(t\) (\(1 \le t \le 1000\)) — the number of test cases.The first line of each test case contains two integers \(n\) and \(m\) (\(1 \le n \le 10^{18}, 1 \le m \le 10^5\)) — the size of bag and the number of boxes, respectively.The second line of each test case contains \(m\) integers \(a_1, a_2, \dots , a_m\) (\(1 \le a_i \le 10^9\)) — the sizes of boxes. It is guaranteed that each \(a_i\) is a power of two.It is also guaranteed that sum of all \(m\) over all test cases does not exceed \(10^5\).
For each test case print one integer — the minimum number of divisions required to fill the bag of size \(n\) (or \(-1\), if it is impossible).