Description

X is a famous engineer. He has to finish n (1<=n<17) project, but he does not have enough time. Thus he decides to employ some workers to do these projects. Now there are m (1<=m<=100) people applying for the job, and each of them can finish some projects alone. However, the engineer has to pay to them. X wants to pay least money to hire some employees to do these n projects. So how can he choose?

Input

Every group of test data starts with two rows, first row includes a number n and the next one includes a number m. And then there are n rows, each row includes a character string that is less than 30 and composed by lowercases, and the string means the name of the project. Finally, there are m rows, each row has two positive integers which is a and b (a means the payment for this employee, and b means he or she can finish b projects alone), following with these two integers there are b names of the projects he or she can finish.

Output

For each group of test data, we print out a positive integer means the least payment X needs to pay for the n projects. If X cannot finish these n projects, print out -1.

Sample Input


5 5
a
b
c
d
e
1000 5 a b c d e
10 2 a b
100 3 c d e
111 3 a c e
50 4 a c d e
5 4
a
b
c
d
e
100 1 a
100 2 a b
100 3 a b c
100 4 a b c d


Sample Output


60
-1


Source

怎么每人看啊？

我看的 可以e文的看不懂

可以->可是