Graph Cost

2000ms

262144K

Description:

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.

Input:

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

Output:

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

Sample Input:

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1731E