给您一个最初为空的无向图,其中包含 $$$n$$$ 节点,编号从 $$$1$$$ 到 $$$n$$$(即 $$$n$$$ 节点和 $$$0$$$ 边)。您想要向图中添加 $$$m$$$ 边,因此该图不会包含任何自循环或多条边。
如果添加连接两个节点 $$$u$$$ 和 $$$v$$$ 的边,则其权重必须等于 $$$u$$$ 和 $$$v$$$ 的最大公约数,i。 e. $$$\gcd(u, v)$$$。
为了向图中添加边,您可以重复以下过程任意次数(可能为零):
- 选择一个整数 $$$k \ge 1$$$;
- 将 $$$k$$$ 边精确添加到图表中,每个边的权重等于 $$$k + 1$$$。添加这些 $$$k$$$ 边总共花费 $$$k + 1$$$。
例如,如果您可以在权重 $$$6$$$ 的图表中添加 $$$5$$$ 的边,则可以添加它们,并且整包 $$$5$$$ 边的成本为 $$$6$$$。但如果您只能将权重为 $$$6$$$ 的 $$$4$$$ 边添加到图中,则无法对 $$$k = 5$$$ 执行此操作。
给定两个整数 $$$n$$$ 和 $$$m$$$,使用上述操作找到形成 $$$n$$$ 个顶点和 $$$m$$$ 边的图的最小总成本。如果无法构建这样的图,则输出$$$-1$$$。
请注意,最终图形可能由多个连接的组件组成。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 10^6$$$; $$$1 \leq m \leq \frac{n(n-1)}{2}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,打印构建该图的最低成本,如果无法构建这样的图,则打印 $$$-1$$$。
示例
输入 #1
4 4 1 6 10 9 4 10 11
输出 #1
2 -1 7 21
注意
在第一个测试用例中,我们可以在顶点 $$$2$$$ 和 $$$4$$$ 之间添加一条边,其中 $$$\gcd = 2$$$。这是添加 $$$1$$$ 优势的唯一可能方法,成本为 $$$2$$$。
在第二个测试用例中,无法添加 $$$10$$$ 边,因此答案是 $$$-1$$$。
在第三个测试用例中,我们可以添加以下边:
- $$$k = 1$$$:顶点 $$$2$$$ 和 $$$4$$$ 之间权重 $$$2$$$ 的边 ($$$\gcd(2, 4) = 2$$$)。费用:$$$2$$$;
- $$$k = 1$$$:顶点 $$$4$$$ 和 $$$6$$$ 之间权重 $$$2$$$ 的边 ($$$\gcd(4, 6) = 2$$$)。费用:$$$2$$$;
- $$$k = 2$$$:权重边 $$$3$$$:$$$(3, 6)$$$ 和 $$$(3, 9)$$$ ($$$\gcd(3, 6) = \gcd(3, 9) = 3$$$)。成本:$$$3$$$。