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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

4
4 1
6 10
9 4
10 11

输出样例 #1

2
-1
7
21

说明

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.

题意翻译

给定 $n$ 个点无边的无向图，连接点 $u$ 和 $v$ 需要满足边权为 $gcd(u,v)$，每次操作可以连接 $k$ 条边权为 $k+1$ 的边，代价为 $k+1$ ，问恰好连接到 $m$ 条边的最小代价。