E. Graph Costtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputEach 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. OutputFor each test case, print the minimum cost to build the graph, or -1 if you can't build such a graph.ExampleInput
44 16 109 410 11Output
2
-1
7
21
NoteIn 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.
44 16 109 410 11
2 -1 7 21 
['dp', 'greedy', 'math', 'number theory', '*2000']