We forbid performing the operation of “connecting Vertex \(x\) and Vertex \((x+A_i) \bmod N\)” for the same pair \((i, x)\) twice or more. (Obviously such a repetition is redundant, so adding such a constraint does not change the answer.)

Let us denote by \(G_t\) the graph in which for each pair of \(i = 1, 2, \ldots, t\) and \(x = 0, 1, 2, \ldots, N-1\), there is an edge of cost \(C_i\) between Vertex \(x\) and Vertex \((x+A_i) \bmod N\). So, \(G_t\) is a graph in which every edge allowed by Operations \(1\) to \(t\) is added, with its cost being the cost required to add the edge.
The original problem is equivalent to that of finding the minimum spanning tree.

Kruskal’s algorithm is an algorithm for solving minimum-spanning-tree problems. Given a weighted undirected graph \(G\), it constructs one of the minimum spanning tree \(T\).
While we don’t explain in detail, the outline of the algorithm is:

• starting from a graph \(T\) with the same vertex set as \(G\) and with no edge,
• add each of the edges of \(G\) in the increasing order of its cost to \(T\) as long as it is “addable.” An edge is said to be “addable” if by adding it to \(T\) the number of connected components of \(T\) decreases by one.

The time complexity of Kruskal’s algorithm is \(\mathrm{O}(E \log E)\), where \(E\) is the number of edges in \(G\).

However, in this problem the graph has \(NM\) edges, so applying Kruskal’s algorithm directly does not finish in time. Instead, we will try to simulate the process of Kruskal’s algorithm fast.
First we sort \(C_i\) in the increasing order, so that we can hereinafter assume \(C_1 \leq C_2 \leq \cdots \leq C_M\). In Kruskal’s algorithm, we add edges to \(T\) in the increasing order of their costs as long as addable; the application for \(G_M\) will be like

• First, we add edges to \(T\) as much as addable with Operation \(1\), which requires the minimum cost;
• then we add to \(T\) as much as addable with Operation \(2\);
• then we add to \(T\) as much as addable with Operation \(3\);
• and all the operations till Operation \(M\) are repeated similarly.

Let \(X_t\) be the number of connected components of \(G_t\), then the number of edges added by the step of “adding as much edges as possible with Operation \(t\)” is \(X_{t-1} - X_t\). (Here we define \(X_0 := N\).) Therefore the answer for the problem is \(\displaystyle \sum_{t=1}^M C_t (X_{t-1} - X_t)\). If \(X_M \gt 1\) nevertheless, then \(G_M\) is not connected and \(G_M\) will not have a spanning tree, so we output \(-1\).

All that left is to find the number of connected component \(X_t\) of \(G_t\) for each \(t = 0, 1, 2, \ldots, M\). We now consider finding \(X_t\).
On \(G_t\), for any \(i = 1, 2, \ldots, t\) and any \(x = 0, 1, \ldots, N-1\), we can move from Vertex \(x\) to Vertex \((x+A_i) \bmod N\) (or vice versa) along an edge, so on \(G_t\), one can travel from \(v\) to \(w\) if and only if “there exist integers \( k_1, k_2, \ldots,\) and \(k_t\) such that \(w \equiv v + k_1 A_1 + k_2 A_2 + \cdots + k_t A_t \pmod N\).” This condition is equivalent to as follows.

There exist integers \( k_1, k_2, \ldots,\) and \(k_t\) such that \(w \equiv v + k_1 A_1 + k_2 A_2 + \cdots + k_t A_t \pmod N\).
\(\Leftrightarrow\) There exist integers \( k_1, k_2, \ldots,\) and \(k_t\) such that \(w = v + k_0 N + k_1 A_1 + k_2 A_2 + \cdots + k_t A_t\).
\(\Leftrightarrow\) There exists an integer \(k\) such that \(w = v + kd_t\).
\(\Leftrightarrow\) \(w \equiv v \pmod {d_t}\)

Here, \(d_t := \gcd(N, A_1, A_2, \ldots, A_t)\).
Therefore, Vertex \(v\) and Vertex \(w\) belong to the same connected component if and only if \(w \equiv v \pmod {d_t}\), so \(X_t\), the number of connected components in \(G_t\), is \(d_t\).