102104: [AtCoder]ABC210 E - Ring MST
Description
Score : $500$ points
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$.
Input
题意翻译
### 题目描述 - 给定一张 $n$ 个点的图，顶点的编号为 $[0, n - 1]$，同时给出两个长度为 $m$ 的数组 $a_1, a_2, \cdots, a_m$ 和 $b_1, b_2, \cdots, b_m$。 - 初始时图中并没有任何边，你可以按照以下操作加边：选择一个 $1 \le i \le m$ 和一个 $0 < x < n$，并在顶点 $x$ 和顶点 $(x + a_i) \bmod n$ 中添加一条长度为 $b_i$ 的边。 - 你现在想要知道，你添加的边的长度总和至少为多少，才能使得整个图连通?如果无论如何都不能使整个图连通，输出 `-1`。 ### 输入格式 - 第一行包含两个整数 $n, m$，分别表示图的顶点个数和数组的数组的长度。 - 接下来 $m$ 行，第 $i$ 行包含两个整数 $a_i, b_i\space(1 \le a_i \le n - 1)$。 ### 输出格式 - 输出一个数，表示答案。 ### 数据范围 - 对于 $30 \%$ 的数据：$1 \le n, m \le 1000, 1 \le b_i \le 10^9$。 - 对于 $60 \%$ 的数据：$1 \le n, m \le 10^5, 1 \le b_i \le 10^9$。 - 对于 $100 \%$ 的数据：$1 \le n \le 10^9, 1 \le m \le 10^5, 1 \le b_i \le 10^9$。 翻译提供者：[Sunrize](https://www.luogu.com.cn/user/502658)。Output
问题描述
我们有一个有$N$个顶点，但没有边的无向图。让我们将这$N$个顶点称为顶点$0$，顶点$1$，顶点$2$，$\ldots$，顶点$N-1$。
考虑对这个图执行$M$种操作。
对于每种操作$i = 1, 2, \ldots, M$，第$i$种操作是选择一个整数$x$，满足$0 \leq x \lt N$，并添加一条连接顶点$x$和顶点$(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$。
样例输入1
4 2 2 3 3 5
样例输出1
11
如果首先执行第一种操作连接顶点$0$和$2$，然后再次执行以连接顶点$1$和$3$，最后执行第二种操作连接顶点$1$和$0$，图就会连通。 这里产生的总费用是$3+3+5 = 11$日元，这是可能的最小费用。
样例输入2
6 1 3 4
样例输出2
-1
无法使图连通，所以应该输出$-1$。