该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

GGB非常想参加天梯赛.但是比赛的题目太复杂了,所以他安排他的$n$个朋友帮他解决这些问题。

在比赛中会有$m$道题目提供给参赛者.对于每个朋友,GGB知道他能解决什么问题.但是GGB的朋友不会无偿的去帮助GGB的, 第$i$个朋友会因为帮助GGB解决所有他会的问题而向GGB索要$x$卢布.并且,只有在GGB陪他至少吃$k$顿大餐时,这个朋友才会去帮助GGB写代码.且每顿大餐需要花费$b$卢布。

GGB很节约用钱,所以他希望尽可能少的花钱去解决所有问题.请你帮助GGB,告诉他怎样花费最少的钱.最初,GGB没有请过任何人吃过大餐.并且,需要注意的是,为了简化问题,这里规定一顿大餐可以邀请的人数没有限制.

输入格式

第一行包含三个整数 $n$, $m$ 和 $b$. 其中,$n$代表GGB的总朋友数,$m$代表问题数,$b$代表一顿大餐的花费

接下来的 $2n$ 行描述每个朋友.第 $2i$ 和 $(2i+1)$ 行包含第$i$个朋友的信息.

第 $2i$ 行包含三个整数 $x_i, k_i, m_i$. 其中, $x_i$表示这个朋友解决题目需要得到的钱, $k_i$表示大餐数量需求, $m_i$表示这个朋友能解决的问题的数目.

第 $(2i+1)$ 行包括$m_i$个不同的正整数 — 第$i$个朋友所能解决的问题的编号. 所有的问题按$1$ ~ $m$编上了序号。

输出格式

输出最小花费, 如果不能完成所有问题, 输出 -1

输入输出样例 #1

输入 #1

2 2 1
100 1 1
2
100 2 1
1

输出 #1

202

输入输出样例 #2

输入 #2

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

输出 #2

205

输入输出样例 #3

输入 #3

1 2 1
1 1 1
1

输出 #3

-1

数据范围

对于100%数据,保证 $1\leq n \leq 100, 1\leq m\leq 20, 1\leq b\leq 10^9, 1\leq x_i\leq 10^9,1\leq k_i\leq 10^9, 1\leq m_i\leq m$