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

你有一个容量为 $n$ 的袋子。此外，你有 $m$ 个盒子。第 $i$ 个盒子的大小为 $a_i$，其中每个 $a_i$ 均为非负整数幂（即形如 $2^k$，其中 $k \ge 0$ 的整数）。

你可以将任意一个盒子均分为两个大小相等的部分。你的目标是恰好装满整个袋子（即所选盒子（或其分割后部分）的大小之和恰好等于 $n$）。

例如，若 $n = 10$ 且 $a = [1, 1, 32]$，则你需要先将大小为 $32$ 的盒子分成两个大小为 $16$ 的部分，再将其中一个大小为 $16$ 的部分继续分割（得到两个大小为 $8$ 的部分）。最终可使用大小为 $1$、$1$ 和 $8$ 的三个盒子恰好填满袋子。

请计算填满容量为 $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$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^{18},\ 1 \le m \le 10^5$）—— 分别表示袋子的容量和箱子的数量。

每个测试用例的第二行包含 $m$ 个整数 $a_1, a_2, \dots , a_m$（$1 \le a_i \le 10^9$）—— 表示各个箱子的大小。保证每个 $a_i$ 均为 2 的幂。

还保证所有测试用例中 $m$ 的总和不超过 $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).

对于每个测试用例，输出一个整数——填满容量为 $n$ 的袋子所需的最少分割次数（若无法实现，则输出 $-1$）。