E - 环最小生成树

得分：500 分

问题描述

我们有一个有 $N$ 个顶点和 $0$ 条边的无向图。 我们将顶点称为 Vertex $0$, Vertex $1$, Vertex $2$, $\ldots$, Vertex $N-1$。

考虑 $M$ 种操作。
对于每个 $i = 1, 2, \ldots, M$，第 $i$ 种操作是选择一个整数 $x$，满足 $0 \leq x \lt N$，并且添加一条连接顶点 Vertex $x$ 和 Vertex $(x + A_i) \bmod N$ 的无向边。这里，$a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

每次执行第 $i$ 种操作的成本是 $C_i$ 日元。

可以按任意顺序进行这 $M$ 种操作任意次数（可能为零）。例如，如果有三种操作可选，可以选择执行第一种操作两次，第二种操作零次，第三种操作一次。

确定是否可以使图连通。如果可以，找到使图连通所需的最小总成本。

约束条件

• $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$
• 输入的所有值都是整数。

输入

从标准输入中按以下格式给出输入：

$N$ $M$

$A_1$ $C_1$

$A_2$ $C_2$

$\vdots$

$A_M$ $C_M$

输出

如果可以使图连通，输出使图连通所需的最小总成本。
如果无法使图连通，输出 $-1$。

4 2
2 3
3 5

11

如果我们首先执行第一种操作，将顶点 $0$ 和顶点 $2$ 连接，然后再执行一次相同操作将顶点 $1$ 和顶点 $3$ 连接，最后执行第二种操作将顶点 $1$ 和顶点 $0$ 连接，图将连通。
这里所需的总成本是 $3+3+5 = 11$ 日元，即为最小值。

6 1
3 4

-1

无法使图连通，所以应该输出 $-1$。