/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の頂点と 0 本の辺からなる無向グラフがあります。 N 個の頂点をそれぞれ頂点 0、頂点 1、頂点 2、\ldots、頂点 N-1と呼びます。
このグラフに対する M 種類の操作を考えます。
i = 1, 2, \ldots, M について、i 番目の操作は「 0 \leq x \lt N を満たす整数 x を選び、頂点 x と頂点 (x + A_i) \bmod N を結ぶ無向辺を追加する」という操作です。ただし、a \bmod b は a を b で割った余りを表します。
i 番目の操作を 1 回行うと C_i 円の費用がかかります。
あなたは、M 種類の操作をそれぞれ好きな回数（ 0 回でもよい）行うことができます。 例えば、3 種類の操作がある場合、1 番目の操作を 2 回、2 番目の操作を 0 回、3 番目の操作を 1 回行うという選択が可能です。
グラフを連結にすることが可能かどうかを判定し、可能な場合はそのためにかかる費用の合計として考えられる最小値を求めてください。
制約
- 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
まず 1 番目の操作で頂点 0 と頂点 2 を結び、次に 1 番目の操作で頂点 1 と頂点 3 を結び、最後に 2 番目の操作で頂点 1 と頂点 0 を結ぶと、グラフは連結になります。 かかった費用の合計は 3+3+5 = 11 円で、これが考えられる最小値です。
入力例 2
6 1 3 4
出力例 2
-1
どのように操作を行ってもグラフを連結にすることができないので、-1 を出力します。
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.