Score : $500$ points

问题描述

我们有一个含有 $N$ 个顶点且无边的无向图。我们将这 $N$ 个顶点依次称为顶点 $0$, 顶点 $1$, 顶点 $2$, $\ldots$, 顶点 $N-1$。

考虑对这个图进行 $M$ 种操作。 对于每一种 $i = 1, 2, \ldots, M$，第 $i$ 种操作是选择一个整数 $x$ 使得 $0 \leq x < N$，并添加一条连接顶点 $x$ 和顶点 $(x + A_i) \mod N$ 的无向边。这里，$a \bmod b$ 表示将 $a$ 除以 $b$ 后的余数。执行一次第 $i$ 种操作需要花费 $C_i$ 日元。

你可以以任意顺序执行这 $M$ 种操作任意次（包括零次）。例如，如果有三种操作可选，你可以选择执行第一种操作两次，第二种操作零次，以及执行第三次操作一次。

确定是否可能使该图变得连通。如果可能的话，找出实现这一目标所需的最小总成本。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have an undirected graph with $N$ vertices and $0$ edges. Let us call the $N$ vertices Vertex $0$, Vertex $1$, Vertex $2$, $\ldots$, Vertex $N-1$.

Consider $M$ kinds of operations on this graph.
For each $i = 1, 2, \ldots, M$, the operation of the $i$-th kind is to choose an integer $x$ such that $0 \leq x \lt N$ and add an undirected edge connecting Vertex $x$ and Vertex $(x + A_i) \bmod N$. Here, $a \bmod b$ denotes the remainder when dividing $a$ by $b$. It costs $C_i$ yen to do the operation of the $i$-th kind once.

You can do these $M$ kinds of operations any number of times (possibly zero) in any order. For example, if three kinds of operations are available, you can choose to do the first operation twice, the second zero times, and the third once.

Determine whether it is possible to make the graph connected. If it is possible, find the minimum total cost needed to do so.

Constraints

• $2 \leq N \leq 10^9$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq N-1$
• $1 \leq C_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $C_1$

$A_2$ $C_2$

$\vdots$

$A_M$ $C_M$

Output

If it is possible to make the graph connected, print the minimum total cost needed to do so.
If it is impossible to make the graph connected, print $-1$.

Sample Input 1

4 2
2 3
3 5

Sample Output 1

11

If we first do the operation of the first kind to connect Vertices $0$ and $2$, then do it again to connect Vertices $1$ and $3$, and finally the operation of the second kind to connect Vertices $1$ and $0$, the graph will be connected. The total cost incurred here is $3+3+5 = 11$ yen, which is the minimum possible.

Sample Input 2

6 1
3 4

Sample Output 2

-1

There is no way to make the graph connected, so we should print $-1$.

update @ 2024/3/10 09:25:09