一个名叫 Gena 的男孩非常想进入“俄罗斯代码杯”决赛,或者至少获得一件 T 恤。但提出的问题太复杂了,所以他和他的n个朋友做了一个安排,让他们来帮他解决问题。
向参与者提供了有关竞赛的问题。对于每个朋友,吉纳都知道他可以解决什么问题。但吉纳的朋友们不会无缘无故地同意帮助吉纳:第 i 个朋友请求吉纳 xi 卢布帮助他解决所有他能解决的问题。另外,朋友同意为 Gena 编写代码,前提是 Gena 的计算机连接到至少 ki 个显示器,每个显示器花费 b 卢布。
吉纳对钱很谨慎,所以他想花尽可能少的钱来解决所有问题。帮助吉纳,告诉他如何花尽可能少的钱。最初,Gena 的计算机上没有连接任何监视器。
输入
第一行包含三个整数 n、m 和 b(1 ≤ n ≤ 100;1 ≤ m ≤ 20;1 ≤ b ≤ 109)——Gena 的好友数量、问题数量和单个显示器的成本。
下面2n行描述了这位朋友。第 2i 行和 (2i + 1) 行包含第 i 个朋友的信息。第 2i 行包含三个整数 xi、ki 和 mi(1 ≤ xi ≤ 109;1 ≤ ki ≤ 109;1 ≤ mi ≤ m)——所需的金额、监视器以及朋友可以解决的问题数量。第 (2i + 1) 行包含 mi 个不同的正整数——第 i 个朋友可以解决的问题数。问题从 1 到 m 编号。
输出
打印吉娜解决所有问题所需花费的最低金额。如果无法实现,则打印 -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