MST.
解法から攻めるのは邪道な気もするが， 問題の性質から攻めて綺麗な方法が作れなかったので， MST のアルゴリズムであるクラスカル法から攻める． クラスカル法により，コストの小さい辺から追加していく． 計算量を無視すればこれで解ける．
高速化
頂点の個数 \(N\) が大きいので，そのままクラスカル法を実装できない． そこで，操作をまとめて行う． コスト \(c_{i}\) が小さい \(i\) を固定して考える． \(+ a_{i}\) の辺を用いて類別する．
\(+ a_{i}\) の辺を追加する操作を何回するのかを数える． そのためには，各類毎に操作を何回するか，類の個数はいくつか， が分かれば十分．
\(g := GCD(N, a_{i})\) とおく． 類毎に \(\frac{N}{g} - 1\) 回， 類が \(g\) 個 あるので，合計 \(g (\frac{N}{g} - 1)\) 回行う． これにコスト \(c_{i}\) を掛ける．
実装では，Union-Find を使う必要はない． 類別した後のグラフが簡単に書けるのが効いている． 新しいグラフは， 頂点数が \(g\) に変わるだけで， \(a\) は変える必要がない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename T>
T GCD( T a, T b ){
const T E = 0; // unit of GCD
if( a == E ) return b;
if( b == E ) return a;
if( a < b ) swap(a,b);
T rem;
do{
rem = a % b;
a = b;
b = rem;
}while( rem != 0 );
return a;
}
int main() {
ll n, m ;
cin >> n >> m;
rep(i,m){
cin >> p[i].second >> p[i].first;
}
sort(all(p));
ll ans = 0;
for(auto [c,a]:p){
ll g = GCD(n, a);
if(g % n == 0) continue;
ans += g*(n/g - 1)*c;
n = g;
if(n == 1) break;
}
if(n != 1) ans = -1;
cout << ans << endl;
return 0;
}
