codeforces#P1408E. Avoid Rainbow Cycles

    ID: 31439 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 9 上传者: 标签>data structuresdsugraphsgreedysortingstrees*2400

Avoid Rainbow Cycles

Description

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 < 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.

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$.

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

Input

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$.

Output

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

Samples

3 2
1 2 3
4 5
2 1 2
2 1 2
2 1 2
11
7 8
3 6 7 9 10 7 239
8 1 9 7 10 2 6 239
3 2 1 3
2 4 1
3 1 3 7
2 4 3
5 3 4 5 6 7
2 5 7
1 8
66

Note

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.