编程援助

题目描述

Y 同学参加了一场共有 $M$ 道题目的编程比赛。由于题目难度过大，Y 同学决定向他的 $N$ 位朋友寻求帮助。

已知第 $i$ 位朋友能够解决特定的 $M_i$ 道题目。然而，让第 $i$ 位朋友帮忙需要满足以下两个条件：

1. Y 同学必须向该朋友支付 $X_i$ 元的代写费用。
2. Y 同学必须为自己的电脑配置至少 $K_i$ 台显示器，该朋友才会开始代写代码。

目前 Y 同学的电脑没有连接任何显示器。他可以在市场上购买显示器，每台显示器的价格固定为 $B$ 元。一旦购买了显示器，其数量就可以用于满足任意多位朋友的要求（即显示器是可复用且共享的）。

Y 同学希望以最小的总花费（购买显示器的总费用加上支付给朋友们的代写费用总和）来解决这 $M$ 道题目。请你编写程序帮助 Y 同学计算出完成目标所需的最小花费。如果无法解决所有的 $M$ 道题目，请输出 $-1$。

输入格式

第一行包含三个整数 $N, M, B$，分别表示朋友的人数、比赛题目的数量以及单台显示器的价格。

接下来的 $2N$ 行，每两行描述一位朋友的信息： 第 $2i-1$ 行包含三个整数 $X_i, K_i, M_i$，分别表示第 $i$ 位朋友要求的代写费用、所需的显示器数量以及他能解决的题目数量。 第 $2i$ 行包含 $M_i$ 个互不相同的整数，表示第 $i$ 位朋友能够解决的题目编号（题目编号从 $1$ 到 $M$），相邻两个整数之间由一个空格隔开。

输出格式

输出一行一个整数，表示 Y 同学解决所有题目需要花费的最低金额。如果无论如何也无法解决所有题目，请输出 -1。

样例

样例输入 #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

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 100$，$1 \le M \le 20$，$1 \le B \le 10^9$，$1 \le X_i, K_i \le 10^9$，$1 \le M_i \le M$。

本题的最小花费可能超过 32 位有符号整数的表示范围，请务必使用 64 位整数类型进行计算与输出。