23581번 - Clique Festival 다국어

John has a graph with $n$ vertices labeled with integers $1, \ldots, n$. Initially, there are no edges in the graph. Then John modifies the graph $k$ times, each time adding a clique to the graph. He chooses an integer $a$ and a set $S$ which is a non-empty subset of the set of integers $1, 2, \ldots, n$. For each unordered pair $(i, j)$ such that $i, j \in S$ and $i \neq j$, John adds an undirected edge between the vertices $i$ and $j$ with weight $a$. It is possible that parallel edges appear in John's graph.

The distance between vertices $u$ and $v$ is defined as follows. Denote $d_{u,v}$ as the minimum weight of the edge between vertices $u$ and $v$, or $\infty$ if there is no such edge. Then $\mathrm{dist}(u,v) = \min\limits_{i_1, \ldots, i_p} \left(d_{u,i_1} + d_{i_1,i_2} + \ldots + d_{i_{p-1},i_p} + d_{i_p,v}\right)$. In other words, the distance is the length of the shortest path between $u$ and $v$.

Your task is to calculate $\sum\limits_{i=1}^{n-1} \sum\limits_{j = i+1}^n dist(i,j)$. It is guaranteed that all summands are finite.

The first line contains two integers $n$ and $k$ ($1 \le n \le 100\,000$, $1 \le k \le 18$). The next $k$ lines contain the descriptions of the added cliques. Each of these lines contains integers $a$ ($1 \le a \le 10^7$), $|S|$ ($1 \le |S| \le n$), and then $|S|$ integers $s_1, \ldots, s_{|S|}$ ($1 \le s_i \le n$, all $s_i$ are distinct). These are the weight of edges in the clique, the number of vertices in the clique, and the labels of these vertices, respectively.

The sum of all $|S|$ in the input does not exceed $300\,000$.

Output a single integer: the answer to the problem.