配点 : $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$ を出力せよ。

4 2
2 3
3 5

11

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

6 1
3 4

-1

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