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.
