#P1408E. Avoid Rainbow Cycles

    ID: 5552 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>data structuresdsugraphsgreedysortingstrees*2400

Avoid Rainbow Cycles

No submission language available for this problem.

Description

You are given mm sets of integers A1,A2,,AmA_1, A_2, \ldots, A_m; elements of these sets are integers between 11 and nn, inclusive.

There are two arrays of positive integers a1,a2,,ama_1, a_2, \ldots, a_m and b1,b2,,bnb_1, b_2, \ldots, b_n.

In one operation you can delete an element jj from the set AiA_i and pay ai+bja_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 nn vertices. For each set AiA_i you will add an edge (x,y)(x, y) with color ii for all x,yAix, y \in A_i and x<yx < y. Some pairs of vertices can be connected with more than one edge, but such edges have different colors.

You call a cycle i1e1i2e2ikeki1i_1 \to e_1 \to i_2 \to e_2 \to \ldots \to i_k \to e_k \to i_1 (eje_j is some edge connecting vertices iji_j and ij+1i_{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 mm and nn (1m,n1051 \leq m, n \leq 10^5), the number of sets and the number of vertices in the graph.

The second line contains mm integers a1,a2,,ama_1, a_2, \ldots, a_m (1ai1091 \leq a_i \leq 10^9).

The third line contains nn integers b1,b2,,bnb_1, b_2, \ldots, b_n (1bi1091 \leq b_i \leq 10^9).

In the each of the next of mm lines there are descriptions of sets. In the ii-th line the first integer sis_i (1sin1 \leq s_i \leq n) is equal to the size of AiA_i. Then sis_i integers follow: the elements of the set AiA_i. These integers are from 11 to nn and distinct.

It is guaranteed that the sum of sis_i for all 1im1 \leq i \leq m does not exceed 21052 \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 mm and nn (1m,n1051 \leq m, n \leq 10^5), the number of sets and the number of vertices in the graph.

The second line contains mm integers a1,a2,,ama_1, a_2, \ldots, a_m (1ai1091 \leq a_i \leq 10^9).

The third line contains nn integers b1,b2,,bnb_1, b_2, \ldots, b_n (1bi1091 \leq b_i \leq 10^9).

In the each of the next of mm lines there are descriptions of sets. In the ii-th line the first integer sis_i (1sin1 \leq s_i \leq n) is equal to the size of AiA_i. Then sis_i integers follow: the elements of the set AiA_i. These integers are from 11 to nn and distinct.

It is guaranteed that the sum of sis_i for all 1im1 \leq i \leq m does not exceed 21052 \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

Sample Input 1

3 2
1 2 3
4 5
2 1 2
2 1 2
2 1 2

Sample Output 1

11

Sample Input 2

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

Sample Output 2

66

Note

In the first test, you can make such operations:

  • Delete element 11 from set 11. You should pay a1+b1=5a_1 + b_1 = 5 coins for that.
  • Delete element 11 from set 22. You should pay a2+b1=6a_2 + b_1 = 6 coins for that.

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

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

In the second test, you can make such operations:

  • Delete element 11 from set 11. You should pay a1+b1=11a_1 + b_1 = 11 coins for that.
  • Delete element 44 from set 22. You should pay a2+b4=13a_2 + b_4 = 13 coins for that.
  • Delete element 77 from set 33. You should pay a3+b7=13a_3 + b_7 = 13 coins for that.
  • Delete element 44 from set 44. You should pay a4+b4=16a_4 + b_4 = 16 coins for that.
  • Delete element 77 from set 66. You should pay a6+b7=13a_6 + b_7 = 13 coins for that.

You pay 6666 coins in total.

After these operations, the sets will be:

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

We will get the graph:

There are no rainbow cycles in it.