You and your friends are always excited about travelling new destinations, specially if they are cheap.
You have shortlisted D destinations to travel and total possible expenses for everyone in each destination Di (1 <= i <= D). You have decided among yourselves that each person will bear the total expense of the group in a destination. Which means if you have N person in your group you will potentially choose N destinations and decide who will be responsible to bear the expenses for which destination.
While coming to a consensus, you realized that everyone has their own list of preferences which cities they are interested to bear the cost for.
In this problem you have to choose N destinations out of D destinations such that each person can bear the expense of exactly one destination which exists in the preferral destination of that person. Of course, the total sum of the expenses of all destinations must be minimal.
Input
The first line of the input will be two positive integers D and N. The next line will have D number of integers. Each number Di denotes the total expenses for the group in i’th destination. For simplicity you can assume these are ids of destinations.
The next N lines will have information of the preferences of everyone in your group. Each line will start with Pi denoting the number of destinations i’th person prefers, followed by i number of integers ( 1 <= i’th integer <= D) denoting a destination id.
- 1 <= D <= 1000
- 1 <= N <= D
- 1 <= Expense of a single destination <= 10000
The input will be such that there is always one possible way to reach a particular total sum. More formally it’s not possible to have total sum S by two possible sets of destinations s1 and s2.
Output
Output should have one integer denoting the minimum total expenses of selected N destinations.
If it’s not possible to choose N destinations fulfilling the criteria print -1.
Sample
| Input | Output |
|---|---|
3 2 1 5 10 2 1 3 1 1 | 11 |
