环形最小生成树

题目描述

我们有一个具有 $N$ 个顶点、$0$ 条边的无向图。 将顶点称为顶点 $0$、顶点 $1$、顶点 $2$、……、顶点 $N-1$。

考虑对这个图进行 $M$ 种操作。

对于每个 $i = 1, 2, \ldots, M$,第 $i$ 种操作是:选择整数 $x$,满足 $0 \le x \lt N$,并添加一条连接顶点 $x$ 和顶点 $(x + A_i) \bmod N$ 的无向边。这里,$a \bmod b$ 表示 $a$ 除以 $b$ 的余数。 执行一次第 $i$ 种操作需要花费 $C_i$ 日元。

你可以按任意顺序进行这 $M$ 种操作任意次(可以为 0 次)。例如,如果有三种操作,你可以选择第一种操作进行两次、第二种操作进行零次、第三种操作进行一次。

判断能否使图连通。如果可能,输出达成连通所需的最小总费用。

输入格式

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

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

数据范围

• $2 \le N \le 10^9$
• $1 \le M \le 10^5$
• $1 \le A_i \le N-1$
• $1 \le C_i \le 10^9$
• 输入均为整数