Avoid Rainbow Cycles SOLUTIONS GRAKN FORCES 2020

Avoid Rainbow Cycles SOLUTION

You are given m sets of integers A1,A2,…,Am; elements of these sets are integers between 1 and n, inclusive.

There are two arrays of positive integers a1,a2,…,am and b1,b2,…,bn.

In one operation you can delete an element j from the set Ai and pay ai+bj 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 Ai you will add an edge (x,y) with color i for all x,y∈Ai 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 i1→e1→i2→e2→…→ik→ek→i1 (ej is some edge connecting vertices ij and ij+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.

Input

The first line contains two integers m and n (1≤m,n≤105), the number of sets and the number of vertices in the graph.

The second line contains m integers a1,a2,…,am (1≤ai≤109).

The third line contains n integers b1,b2,…,bn (1≤bi≤109).

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

It is guaranteed that the sum of si for all 1≤i≤m does not exceed 2⋅105.

Output

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

Examples

inputCopy

3 2

1 2 3

4 5

2 1 2

2 1 2

2 1 2

outputCopy

11

inputCopy

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

outputCopy

66

Note

In the first test, you can make such operations:

Delete element 1 from set 1. You should pay a1+b1=5 coins for that.

Delete element 1 from set 2. You should pay a2+b1=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 a1+b1=11 coins for that.

Delete element 4 from set 2. You should pay a2+b4=13 coins for that.

Delete element 7 from set 3. You should pay a3+b7=13 coins for that.

Delete element 4 from set 4. You should pay a4+b4=16 coins for that.

Delete element 7 from set 6. You should pay a6+b7=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.

Leave a Comment