CF1303D Fill The Bag

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).