← 返回题目列表

Codeforces · 1303/D

D. 装满袋子

中文机器翻译题面 查看原题

您有一个尺寸为 $$$n$$$ 的包。你还有$$$m$$$盒子。第 $$$i$$$ 个框的大小为 $$$a_i$$$,其中每个 $$$a_i$$$ 是 2 的非负整数幂。

您可以将盒子分成大小相等的两部分。您的目标是完全填满袋子。

例如,如果 $$$n = 10$$$ 且 $$$a = [1, 1, 32]$$$,则必须将大小为 $$$32$$$ 的盒子分成大小为 $$$16$$$ 的两部分,然后将大小为 $$$16$$$ 的盒子分成两部分。因此,您可以在袋子中装满尺寸为 $$$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$$$,如果不可能的话)。

示例

输入 #1

3
10 3
1 32 1
23 4
16 1 4 1
20 5
2 1 16 1 8

输出 #1

2
-1
0