提示: 欢迎访问OurACM平台。
Problem 2165 v11

Accept: 37    Submit: 105
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

v11最近在玩一个游戏。这个游戏有N个BOSS,打败BOSS需要特定的武器。一共有M种武器,每种武器都有价格,每件武器可以使用任意次。现在知道每种武器的价格,以及每种武器分别能打败哪些BOSS,v11想用最小的花费打败所有BOSS,请问最小的费用是多少?

Input

输入包含多组数据。对于每组数据,输入第一行包含两个整数N,M (2<=N,M<=100),表示有N个BOSS,M种武器。接下来输入M行,第i行先输入两个数Ci,Ki(1<=Ci<=1000000,0<=Ki<=N),表示第i种武器价格为Ci,能打败Ki个BOSS,接着输入Ki个数,表示能打败的BOSS的编号,编号为1到N。

Output

对于每组数据输出一个整数,表示最小费用,若无法打败所有BOSS,则输出-1。

Sample Input

3 4 1 1 1 1 1 2 1 1 3 2 3 1 2 3

Sample Output

2

Submit  Back  Status  Discuss