CF1408E.Avoid Rainbow Cycles

You are given $m$ sets of integers $A_1, A_2, \ldots, A_m$; elements of these sets are integers between $1$ and $n$, inclusive.

There are two arrays of positive integers $a_1, a_2, \ldots, a_m$ and $b_1, b_2, \ldots, b_n$.

In one operation you can delete an element $j$ from the set $A_i$ and pay $a_i + b_j$ coins for that.

You can make several (maybe none) operations (some sets can become empty).

After that, you will make an edge-colored undirected graph consisting of $n$ vertices. For each set $A_i$ you will add an edge $(x, y)$ with color $i$ for all $x, y \in A_i$ and $x \lt y$. Some pairs of vertices can be connected with more than one edge, but such edges have different colors.

You call a cycle $i_1 \to e_1 \to i_2 \to e_2 \to \ldots \to i_k \to e_k \to i_1$ ($e_j$ is some edge connecting vertices $i_j$ and $i_{j+1}$ in this graph) rainbow if all edges on it have different colors.

Find the minimum number of coins you should pay to get a graph without rainbow cycles.

给你 $m$ 个整数集合 $A_1, A_2, \ldots, A_m$；这些集合中的元素均为介于 $1$ 到 $n$（含）之间的整数。

另有两个正整数数组 $a_1, a_2, \ldots, a_m$ 和 $b_1, b_2, \ldots, b_n$。

一次操作定义为：从集合 $A_i$ 中删除一个元素 $j$，并为此支付 $a_i + b_j$ 枚金币。

你可以执行若干次（也可以不执行）此类操作（某些集合可能因此变为空集）。

之后，你将构造一个边染色的无向图，该图包含 $n$ 个顶点。对于每个集合 $A_i$，你将在所有满足 $x, y \in A_i$ 且 $x \lt y$ 的顶点对 $(x, y)$ 之间添加一条颜色为 $i$ 的边。某些顶点对之间可能被多条边连接，但这些边的颜色互不相同。

我们称一个环 $i_1 \to e_1 \to i_2 \to e_2 \to \ldots \to i_k \to e_k \to i_1$（其中每条边 $e_j$ 连接顶点 $i_j$ 和 $i_{j+1}$，且下标按模 $k$ 计算）为彩虹环（rainbow cycle），当且仅当该环上所有边的颜色互不相同。

求使最终图中不存在彩虹环所需支付的金币数的最小值。

The first line contains two integers $m$ and $n$ ($1 \leq m, n \leq 10^5$), the number of sets and the number of vertices in the graph.

The second line contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \leq a_i \leq 10^9$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$).

In the each of the next of $m$ lines there are descriptions of sets. In the $i$-th line the first integer $s_i$ ($1 \leq s_i \leq n$) is equal to the size of $A_i$. Then $s_i$ integers follow: the elements of the set $A_i$. These integers are from $1$ to $n$ and distinct.

It is guaranteed that the sum of $s_i$ for all $1 \leq i \leq m$ does not exceed $2 \cdot 10^5$.

第一行包含两个整数 $m$ 和 $n$（$1 \leq m, n \leq 10^5$），分别表示集合的数量和图中顶点的数量。

第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$（$1 \leq a_i \leq 10^9$）。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$）。

接下来的 $m$ 行中，每行描述一个集合。第 $i$ 行的第一个整数 $s_i$（$1 \leq s_i \leq n$）表示集合 $A_i$ 的大小；随后是 $s_i$ 个整数：集合 $A_i$ 的元素。这些整数均在 $1$ 到 $n$ 之间，且互不相同。

保证对所有 $1 \leq i \leq m$，所有 $s_i$ 的总和不超过 $2 \cdot 10^5$。

Print one integer: the minimum number of coins you should pay for operations to avoid rainbow cycles in the obtained graph.

输出一个整数：为避免所得图中出现彩虹环，你需要支付的最少硬币数量。

In the first test, you can make such operations:

• Delete element $1$ from set $1$. You should pay $a_1 + b_1 = 5$ coins for that.
• Delete element $1$ from set $2$. You should pay $a_2 + b_1 = 6$ coins for that.

You pay $11$ coins in total. After these operations, the first and the second sets will be equal to ${2}$ and the third set will be equal to ${1, 2}$.

So, the graph will consist of one edge $(1, 2)$ of color $3$.

In the second test, you can make such operations:

• Delete element $1$ from set $1$. You should pay $a_1 + b_1 = 11$ coins for that.
• Delete element $4$ from set $2$. You should pay $a_2 + b_4 = 13$ coins for that.
• Delete element $7$ from set $3$. You should pay $a_3 + b_7 = 13$ coins for that.
• Delete element $4$ from set $4$. You should pay $a_4 + b_4 = 16$ coins for that.
• Delete element $7$ from set $6$. You should pay $a_6 + b_7 = 13$ coins for that.

You pay $66$ coins in total.

After these operations, the sets will be:

• ${2, 3}$;
• ${1}$;
• ${1, 3}$;
• ${3}$;
• ${3, 4, 5, 6, 7}$;
• ${5}$;
• ${8}$.

We will get the graph:

There are no rainbow cycles in it.

在第一个测试用例中，你可以执行如下操作：

• 从集合 $1$ 中删除元素 $1$。为此你需要支付 $a_1 + b_1 = 5$ 枚金币。
• 从集合 $2$ 中删除元素 $1$。为此你需要支付 $a_2 + b_1 = 6$ 枚金币。

你总共支付了 $11$ 枚金币。执行这些操作后，第一个和第二个集合均变为 $\{2\}$，第三个集合变为 $\{1, 2\}$。

因此，所得图包含一条颜色为 $3$ 的边 $(1, 2)$。

在第二个测试用例中，你可以执行如下操作：

• 从集合 $1$ 中删除元素 $1$。为此你需要支付 $a_1 + b_1 = 11$ 枚金币。
• 从集合 $2$ 中删除元素 $4$。为此你需要支付 $a_2 + b_4 = 13$ 枚金币。
• 从集合 $3$ 中删除元素 $7$。为此你需要支付 $a_3 + b_7 = 13$ 枚金币。
• 从集合 $4$ 中删除元素 $4$。为此你需要支付 $a_4 + b_4 = 16$ 枚金币。
• 从集合 $6$ 中删除元素 $7$。为此你需要支付 $a_6 + b_7 = 13$ 枚金币。

你总共支付了 $66$ 枚金币。

执行这些操作后，各集合变为：

• $\{2, 3\}$；
• $\{1\}$；
• $\{1, 3\}$；
• $\{3\}$；
• $\{3, 4, 5, 6, 7\}$；
• $\{5\}$；
• $\{8\}$。

我们得到如下图：

该图中不存在彩虹环。