#P1408E. Avoid Rainbow Cycles
Avoid Rainbow Cycles
No submission language available for this problem.
Description
You are given sets of integers ; elements of these sets are integers between and , inclusive.
There are two arrays of positive integers and .
In one operation you can delete an element from the set and pay 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 vertices. For each set you will add an edge with color for all and . Some pairs of vertices can be connected with more than one edge, but such edges have different colors.
You call a cycle ( is some edge connecting vertices and 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 and (), the number of sets and the number of vertices in the graph.
The second line contains integers ().
The third line contains integers ().
In the each of the next of lines there are descriptions of sets. In the -th line the first integer () is equal to the size of . Then integers follow: the elements of the set . These integers are from to and distinct.
It is guaranteed that the sum of for all does not exceed .
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 and (), the number of sets and the number of vertices in the graph.
The second line contains integers ().
The third line contains integers ().
In the each of the next of lines there are descriptions of sets. In the -th line the first integer () is equal to the size of . Then integers follow: the elements of the set . These integers are from to and distinct.
It is guaranteed that the sum of for all does not exceed .
Output
Print one integer: the minimum number of coins you should pay for operations to avoid rainbow cycles in the obtained graph.
Samples
Note
In the first test, you can make such operations:
- Delete element from set . You should pay coins for that.
- Delete element from set . You should pay coins for that.
You pay coins in total. After these operations, the first and the second sets will be equal to and the third set will be equal to .
So, the graph will consist of one edge of color .
In the second test, you can make such operations:
- Delete element from set . You should pay coins for that.
- Delete element from set . You should pay coins for that.
- Delete element from set . You should pay coins for that.
- Delete element from set . You should pay coins for that.
- Delete element from set . You should pay coins for that.
You pay coins in total.
After these operations, the sets will be:
- ;
- ;
- ;
- ;
- ;
- ;
- .
We will get the graph:
There are no rainbow cycles in it.