Avoid Rainbow Cycles
Contest: Grakn Forces 2020
Difficulty rating: 2400
Tags: data structures, dsu, graphs, greedy, sortings, trees

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.

Input format:
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 format:
Print one integer: the minimum number of coins you should pay for operations to avoid rainbow cycles in the obtained graph.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
3 2
1 2 3
4 5
2 1 2
2 1 2
2 1 2

Example output:
11

Example input:
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

Example output:
66

Editorial:
Let's make a bipartite graph with $$$m$$$ vertices on the left side and $$$n$$$ vertices on the right side.
We will connect vertex $$$i$$$ from the left side with all elements of $$$A_i$$$.
It can be proven, that the graph, which we create using our sets don't have rainbow cycles if and only if our bipartite graph don't have cycles.
So, our task is equivalent of finding the Maximum Spanning Tree of this bipartite graph, where edge between $$$i$$$ (from left side) and $$$j$$$ (from right side) has weight equal to $$$a_i + b_j$$$.