CF1731E.Graph Cost

You are given an initially empty undirected graph with $n$ nodes, numbered from $1$ to $n$ (i. e. $n$ nodes and $0$ edges). You want to add $m$ edges to the graph, so the graph won't contain any self-loop or multiple edges.

If an edge connecting two nodes $u$ and $v$ is added, its weight must be equal to the greatest common divisor of $u$ and $v$, i. e. $\gcd(u, v)$.

In order to add edges to the graph, you can repeat the following process any number of times (possibly zero):

• choose an integer $k \ge 1$;
• add exactly $k$ edges to the graph, each having a weight equal to $k + 1$. Adding these $k$ edges costs $k + 1$ in total.

Note that you can't create self-loops or multiple edges. Also, if you can't add $k$ edges of weight $k + 1$, you can't choose such $k$.

For example, if you can add $5$ more edges to the graph of weight $6$, you may add them, and it will cost $6$ for the whole pack of $5$ edges. But if you can only add $4$ edges of weight $6$ to the graph, you can't perform this operation for $k = 5$.

Given two integers $n$ and $m$, find the minimum total cost to form a graph of $n$ vertices and exactly $m$ edges using the operation above. If such a graph can't be constructed, output $-1$.

Note that the final graph may consist of several connected components.

你被给定一个初始为空的无向图，该图包含 $n$ 个节点，编号从 $1$ 到 $n$（即 $n$ 个节点，$0$ 条边）。你需要向图中添加 $m$ 条边，使得图中不包含任何自环或重边。

若添加一条连接节点 $u$ 和 $v$ 的边，则其权重必须等于 $u$ 与 $v$ 的最大公约数，即 $\gcd(u, v)$。

为了向图中添加边，你可以重复执行以下操作任意次数（包括零次）：

• 选择一个整数 $k \ge 1$；
• 向图中恰好添加 $k$ 条边，每条边的权重均为 $k + 1$。执行该操作的总代价为 $k + 1$。

注意：你不允许创建自环或重边。此外，若无法添加 $k$ 条权重为 $k + 1$ 的边，则不允许选择该 $k$。

例如，若图中尚可添加 $5$ 条权重为 $6$ 的边，则你可以执行该操作（即选择 $k = 5$），并为此付出总代价 $6$。但若图中最多只能添加 $4$ 条权重为 $6$ 的边，则你不能为 $k = 5$ 执行该操作。

给定两个整数 $n$ 和 $m$，求使用上述操作构造一个含 $n$ 个顶点、恰好 $m$ 条边的图所需的最小总代价。若无法构造这样的图，则输出 $-1$。

注意：最终图可能由若干个连通分量组成。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^6$; $1 \leq m \leq \frac{n(n-1)}{2}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print the minimum cost to build the graph, or $-1$ if you can't build such a graph.

对于每个测试用例，输出构建该图的最小代价；如果无法构建这样的图，则输出 $-1$。

In the first test case, we can add an edge between the vertices $2$ and $4$ with $\gcd = 2$. This is the only possible way to add $1$ edge that will cost $2$.

In the second test case, there is no way to add $10$ edges, so the answer is $-1$.

In the third test case, we can add the following edges:

• $k = 1$: edge of weight $2$ between vertices $2$ and $4$ ($\gcd(2, 4) = 2$). Cost: $2$;
• $k = 1$: edge of weight $2$ between vertices $4$ and $6$ ($\gcd(4, 6) = 2$). Cost: $2$;
• $k = 2$: edges of weight $3$: $(3, 6)$ and $(3, 9)$ ($\gcd(3, 6) = \gcd(3, 9) = 3$). Cost: $3$.

As a result, we added $1 + 1 + 2 = 4$ edges with total cost $2 + 2 + 3 = 7$, which is the minimal possible cost.

在第一个测试用例中，我们可以在顶点 $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$。

最终，我们共添加了 $1 + 1 + 2 = 4$ 条边，总代价为 $2 + 2 + 3 = 7$，这是可能的最小总代价。