Cunning Gena

题意翻译

Gena非常想参加“俄罗斯code cup”的决赛，或是至少得到一件T恤。 但是比赛的题目太复杂了，所以他安排他的n个朋友帮他解决这些问题。 在比赛中会有m道题目提供给参赛者。对于每个朋友，Gena知道他能解决什么问题。 但是Gena的朋友不会无偿的去帮助Gena的， 第i个朋友会因为帮助Gena解决所有他会的问题而向Gena索要x卢布。 并且，只有在Gena的电脑连接到至少k台显示器时，这个朋友才会去帮助Gena写代码。 且每台显示器需要花费b卢布。 Gena很节约用钱，所以他希望尽可能少的花钱去解决所有问题。 请你帮助Gena，告诉他怎样花费最少的钱。 最初，Gena的电脑没有连接任何显示器。 输入格式: 第一行包含三个整数 n , m 和 b ( 1<=n<=100 1<=n<=100 ; 1<=m<=20 1<=m<=20 ; 1<=b<=1e9 1<=b<=1e9) 其中， n代表Gena的总朋友数，m代表问题数，b代表一个显示器的花费 接下来的 2n 行描述每个朋友。 第 2i 和 (2i+1) 行包含第i个朋友的信息。 第 2i 行包含三个整数 xi , ki , mi (1<=xi<=1e9 ; 1<=ki<=1e9 ; 1<=mi<=m )其中，xi表示这个朋友解决题目需要得到的钱，ki表示显示器数量需求，mi表示这个朋友能解决的问题的数目。 第 (2i+1) 行包括mi个不同的正整数—第i个朋友所能解决的问题的编号。 所有的问题按1-m编上了序号。 输出格式： 输出最小花费，如果不能完成所有问题，输出-1

题目描述

A boy named Gena really wants to get to the "Russian Code Cup" finals, or at least get a t-shirt. But the offered problems are too complex, so he made an arrangement with his $ n $ friends that they will solve the problems for him. The participants are offered $ m $ problems on the contest. For each friend, Gena knows what problems he can solve. But Gena's friends won't agree to help Gena for nothing: the $ i $ -th friend asks Gena $ x_{i} $ rubles for his help in solving all the problems he can. Also, the friend agreed to write a code for Gena only if Gena's computer is connected to at least $ k_{i} $ monitors, each monitor costs $ b $ rubles. Gena is careful with money, so he wants to spend as little money as possible to solve all the problems. Help Gena, tell him how to spend the smallest possible amount of money. Initially, there's no monitors connected to Gena's computer.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ b $ ( $ 1<=n<=100 $ ; $ 1<=m<=20 $ ; $ 1<=b<=10^{9} $ ) — the number of Gena's friends, the number of problems and the cost of a single monitor. The following $ 2n $ lines describe the friends. Lines number $ 2i $ and $ (2i+1) $ contain the information about the $ i $ -th friend. The $ 2i $ -th line contains three integers $ x_{i} $ , $ k_{i} $ and $ m_{i} $ ( $ 1<=x_{i}<=10^{9} $ ; $ 1<=k_{i}<=10^{9} $ ; $ 1<=m_{i}<=m $ ) — the desired amount of money, monitors and the number of problems the friend can solve. The $ (2i+1) $ -th line contains $ m_{i} $ distinct positive integers — the numbers of problems that the $ i $ -th friend can solve. The problems are numbered from $ 1 $ to $ m $ .

输出格式

Print the minimum amount of money Gena needs to spend to solve all the problems. Or print -1, if this cannot be achieved.

输入输出样例

输入样例 #1

2 2 1
100 1 1
2
100 2 1
1

输出样例 #1

202

输入样例 #2

3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2

输出样例 #2

205

输入样例 #3

1 2 1
1 1 1
1

输出样例 #3

-1