클리크 축제

John에게는 정수 $1, \ldots, n$로 번호가 붙은 $n$개의 정점을 가진 그래프가 있다. 처음에는 그래프에 간선이 없다. 그런 다음 John은 그래프를 $k$번 수정하며, 매번 그래프에 클리크 하나를 추가한다. 그는 정수 $a$와 $1, 2, \ldots, n$의 부분집합 중 공집합이 아닌 집합 $S$를 고른다. $i, j \in S$이고 $i \neq j$인 모든 순서 없는 쌍 $(i, j)$에 대해, John은 정점 $i$와 $j$ 사이에 무게 $a$의 무향 간선을 추가한다. John의 그래프에는 평행 간선이 생길 수 있다.

정점 $u$와 $v$ 사이의 거리는 다음과 같이 정의된다. $d_{u,v}$를 정점 $u$와 $v$ 사이 간선의 최소 무게, 그러한 간선이 없으면 $\infty$로 표기하자. 그러면 $\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)$이다. 즉, 거리는 $u$와 $v$ 사이 최단 경로의 길이이다.

여러분의 과제는 $\sum\limits_{i=1}^{n-1} \sum\limits_{j = i+1}^n dist(i,j)$를 계산하는 것이다. 모든 항이 유한함이 보장된다.

첫째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 100\,000$, $1 \le k \le 18$). 다음 $k$개의 줄에는 추가된 클리크의 설명이 주어진다. 각 줄에는 정수 $a$ ($1 \le a \le 10^7$), $|S|$ ($1 \le |S| \le n$), 그리고 $|S|$개의 정수 $s_1, \ldots, s_{|S|}$ ($1 \le s_i \le n$, 모든 $s_i$는 서로 다름)가 주어진다. 이들은 각각 클리크에 있는 간선의 무게, 클리크에 있는 정점의 수, 정점들의 번호이다.

입력에서 모든 $|S|$의 합은 $300\,000$을 넘지 않는다.

문제의 답을 나타내는 정수 하나를 출력한다.