1703: 开箱
[Creator : ]
Description
一共有N个宝箱。
一个商店里面正在卖M把钥匙。第i把钥匙的价格为ai元，他能打开编号为ci1,ci2,...cibi的宝箱。每把钥匙都可以重复使用。
现在你要通过购买钥匙来打开所有宝箱，请你求出需要的最小花费。如果不存在可行解，输出−1。
一个商店里面正在卖M把钥匙。第i把钥匙的价格为ai元，他能打开编号为ci1,ci2,...cibi的宝箱。每把钥匙都可以重复使用。
现在你要通过购买钥匙来打开所有宝箱，请你求出需要的最小花费。如果不存在可行解，输出−1。
Input
输入的所有数字都为正整数。
输入格式为
输入格式为
Output
输出一个整数，表示最小花费。
Sample Input Copy
2 3
10 1
1
15 1
2
30 2
1 2
Sample Output Copy
25
HINT
1≤N≤12
1≤M≤103
1≤ai≤105
1≤bi≤N
1≤cij≤N
1≤M≤103
1≤ai≤105
1≤bi≤N
1≤cij≤N