题目描述

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$