题目描述

$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$ 回行うという選択が可能です。

グラフを連結にすることが可能かどうかを判定し、可能な場合はそのためにかかる費用の合計として考えられる最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $C_1$ $A_2$ $C_2$ $\vdots$ $A_M$ $C_M$

输出格式

グラフを連結にすることが可能な場合は、そのためにかかる費用の合計として考えられる最小値を出力せよ。
グラフを連結にすることが不可能な場合は、$-1$ を出力せよ。

题目大意

题目描述

• 给定一张 $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 \le 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。

4 2
2 3
3 5

11

6 1
3 4

-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$
• 入力はすべて整数

Sample Explanation 1

まず $1$ 番目の操作で頂点 $0$ と頂点 $2$ を結び、次に $1$ 番目の操作で頂点 $1$ と頂点 $3$ を結び、最後に $2$ 番目の操作で頂点 $1$ と頂点 $0$ を結ぶと、グラフは連結になります。 かかった費用の合計は $3+3+5\ =\ 11$ 円で、これが考えられる最小値です。

Sample Explanation 2

どのように操作を行ってもグラフを連結にすることができないので、$-1$ を出力します。