abc210e - Ring MST

题目描述

有一个包含 $N$ 个顶点、初始没有边的无向图，顶点编号为 $0,1,\ldots,N-1$。

你有 $M$ 种操作。第 $i$ 种操作可以选择任意整数 $x$，满足 $0\le x<N$，并加入一条连接顶点 $x$ 与顶点 $(x+A_i)\bmod N$ 的无向边。每执行一次第 $i$ 种操作，需要花费 $C_i$。

每种操作可以执行任意多次，也可以不执行。请判断能否使图连通；若可以，输出最小总花费，否则输出 -1。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $A_i,C_i$。

输出格式

如果能使图连通，输出最小总花费；否则输出 -1。

样例输入 #1

4 2
2 3
3 5

样例输出 #1

11

样例输入 #2

6 1
3 4

样例输出 #2

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

标签与难度

• 标签：贪心，最大公约数，最小生成树
• 难度：AtCoder 500