在古老的战场上，白魔法师正在与 $n$ 只邪恶生物组成的军队作战。魔法师可以使用 $m$ 种攻击法术。每种法术可以消灭一组特定的敌人，并且施放该法术需要消耗一定的法力值。请注意：

1. 只有当法术目标中的所有生物在施法前都存活时，该法术才能被使用，否则该法术无效。
2. 一旦施放，法术会消灭所有与之相关的生物，魔法师无法控制法术来保护其中的任何生物。

请检查白魔法师是否能够消灭所有邪恶生物，如果可以，求出获胜所需的最少法力值。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 18$)，表示邪恶生物的数量；$m$ ($0 \le m \le 100$)，表示攻击法术的数量。

接下来的 $m$ 行，每行定义一个法术，包含受影响生物的列表：首先是一个整数 $k_i$ ($1 \le k_i \le n$)，表示列表长度；随后是 $k_i$ 个 $1$ 到 $n$ 之间的整数，表示该法术影响的生物编号；最后是一个整数 $v_i$ ($v_i \le 1000$)，表示施放该法术所需的法力值。

输出格式

输出一个整数，表示消灭所有邪恶生物所需的最少法力值。如果无法消灭所有生物，则输出 $-1$。

样例

输入 1

5 6
2 1 2 10
3 3 4 5 18
2 4 5 6
1 3 7
1 2 4
1 1 11

输出 1

23

输入 2

3 2
2 1 2 5
2 2 3 5

输出 2

-1

说明

在第一个样例中，魔法师有 4 种获胜方式：（法术 1 和 2，消耗 28 法力值）、（1, 3, 4，消耗 23）、（2, 5, 6，消耗 33）、（3, 4, 5, 6，消耗 28）。因此，使用 1, 3, 4 是最有效的方式。

在第一个样例中，编号为 2 的生物在施放任何法术后都会被消灭。因此，只能施放其中一个法术，但它无法消灭所有邪恶生物。