CF1303D Fill The Bag

你有一个容量为 $n$ 的袋子，同时有 $m$ 个盒子。第 $i$ 个盒子的大小为 $a_i$，其中每个 $a_i$ 都是非负整数的 $2$ 的幂。 你可以将任意一个盒子分成两个大小相等的部分。你的目标是将袋子完全填满。 例如，如果 $n = 10$，$a = [1, 1, 32]$，那么你需要将大小为 $32$ 的盒子分成两个 $16$，再将 $16$ 分成两个 $8$。这样你可以用 $1$、$1$ 和 $8$ 大小的盒子填满袋子。 请计算最少需要分割多少次，才能将容量为 $n$ 的袋子完全填满。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示将容量为 $n$ 的袋子完全填满所需的最小分割次数（如果无法填满，输出 $-1$）。

由 ChatGPT 4.1 翻译