「頂点 \(x\) と頂点 \((x+A_i) \bmod N\) を辺で結ぶ」操作を同じ \((i, x)\) の組に \(2\) 回以上行うことは、以下では禁止することにします。 （そのようなことは明らかに無駄なので、この制約を追加しても問題の答えは変わりません。)

すべての \(i = 1, 2, \ldots, t\) と \(x = 0, 1, 2, \ldots, N-1\) の組について頂点 \(x\) と頂点 \((x+A_i) \bmod N\) の間に重み \(C_i\) の無向辺を張って得られるグラフを \(G_t\) で表します。 つまり \(G_t\) は、操作 \(1\) から操作 \(t\) までの \(t\) 個の操作のみが許される場合に張ることができる辺をすべて張り、各辺の重みをその辺を引くために必要なコストとしたグラフです。
この問題は、\(G_M\) の最小全域木を重みを求める問題です。

クラスカル法は、最小全域木問題を解くアルゴリズムの一つです。 与えられた重み付き無向グラフ \(G\) から、その最小全域木の一つ \(T\) を構成します。
詳細な説明は省略しますが、アルゴリズムの大まかな流れは、

• \(G\) と同じ頂点集合をもち辺を持たないグラフ \(T\) からはじめ、
• \(G\) の重みの小さい辺から順に \(T\) に「追加できる」限り追加するというものです。ただし、「追加できる」とは、その辺を \(T\) に追加することで \(T\) の連結成分が \(1\) つ減ることを指します。
  

\(G\) の辺数を \(E\) とすると、クラスカル法の時間計算量は \(\mathrm{O}(E \log E)\) です。

しかしこの問題では辺数が \(NM\) 本であるため、クラスカル法をそのまま適用しては実行制限時間に間に合いません。 そこで、クラスカル法の過程を高速にシミュレーションする方法を考えます。
まず操作を \(C_i\) の昇順にソートし、以下では \(C_1 \leq C_2 \leq \cdots \leq C_M\) が成り立つと仮定します。 クラスカル法では重みの小さい辺から順番に、「追加できる」限り \(T\) に追加していくため、\(G_M\) にクラスカル法を適用すると、

• まず、操作のコストが最も小さい操作 \(1\) で辺を「追加できる」限り \(T\) に辺を追加する。
• 操作 \(2\) で辺を「追加できる」限り \(T\) に辺を追加する。
• 操作 \(3\) で辺を「追加できる」限り \(T\) に辺を追加する。
• 同様に操作 \(M\) までこれを繰り返す。

という動作になります。 \(G_{t}\) の連結成分の個数を \(X_t\) とおくと、「操作 \(t\) で辺を追加できる限り辺を追加する」のステップで追加される辺の本数は \(X_{t-1} - X_t\) です。 （ただし、\(X_0 := N\) とします。） よって、この問題の答えは \(\displaystyle \sum_{t=1}^M C_t (X_{t-1} - X_t)\) です。 ただし \(X_M \gt 1\) のときは、\(G_M\) が連結でなく \(G_M\) は全域木を持たないため、\(-1\) を出力します。

あとは、\(t = 0, 1, 2, \ldots, M\) について、\(G_t\) の連結成分の個数 \(X_t\) がわかればこの問題が解けるので、以下で \(X_t\) の値を求めます。
\(G_t\) 上では、任意の \(i = 1, 2, \ldots, t\) と任意の \(x = 0, 1, \ldots, N-1\) について、頂点 \(x\) から頂点 \((x+A_i) \bmod N\) へ（あるいはその逆向きに）辺を辿って移動できるので、 \(G_t\) 上で頂点 \(v\) から頂点 \(w\) へ到達できる必要十分条件は、 「\(w \equiv v + k_1 A_1 + k_2 A_2 + \cdots + k_t A_t \pmod N\) を満たす整数 \( k_1, k_2, \ldots, k_t\) が存在する」ことです。 この条件は次のように言い換えられます。

\(w \equiv v + k_1 A_1 + k_2 A_2 + \cdots + k_t A_t \pmod N\) を満たす整数 \( k_1, k_2, \ldots, k_t\) が存在する。
\(\Leftrightarrow\) \(w = v + k_0 N + k_1 A_1 + k_2 A_2 + \cdots + k_t A_t\) を満たす整数 \(k_0, k_1, k_2, \ldots, k_t\) が存在する。
\(\Leftrightarrow\) \(w = v + kd_t\) を満たす整数 \(k\) が存在する。
\(\Leftrightarrow\) \(w \equiv v \pmod {d_t}\)

です。ただし、\(d_t := \gcd(N, A_1, A_2, \ldots, A_t)\) です。
よって、頂点 \(v\) と頂点 \(w\) が同じ連結成分上にある必要十分条件は \(w \equiv v \pmod {d_t}\) であるので、\(G_t\) の連結成分の個数 \(X_t\) は \(d_t\) 個です。