J. Добрый маг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На поле битвы столкнулись армии добра и зла. В ходе долгого кровопролитного противостояния практически все силы добра были уничтожены. Остался лишь один маг, которому теперь предстоит в одиночку сражаться против армии из n злых существ. К счастью, добрый маг знает m заклинаний, способных уничтожать вражеских существ.

Каждое заклинание способно убить определенное множество врагов, при этом потратится определенное количество магической энергии. Есть две важных особенности использования заклинаний, которые нужно знать:

  1. Заклинание можно использовать лишь в том случае, если все существа, на которые оно действует, живы до момента использования.
  2. Заклинание после использования убьет всех существ, на которые действует. У мага нет возможности пощадить существо, на которое распространяется заклинание.

Сможет ли добрый маг уничтожить всех врагов и принести победу силам добра? Если да, то какое минимальное количество магической энергии для этого потребуется?

Входные данные

В первой строке содержатся два целых числа: n (1 ≤ n ≤ 18) – количество злых существ и m (0 ≤ m ≤ 100) – количество заклинаний.

Следующие m строк содержат информацию о заклинаниях. Первое число строки содержит целое число ki (1 ≤ ki ≤ n) – количество существ, на которых действует i-е заклинание. Далее идет ki целых чисел от 1 до n – номера существ, на которые действует заклинание (будем считать, что злые существа пронумерованы от 1 до n), числа в этом списке не повторяются. Последним в строке идет натуральное число vi (vi ≤ 1000) – количество магической энергии, необходимое для использования заклинания.

Выходные данные

Выведите единственное число – минимальное количество энергии, которое нужно потратить, чтобы уничтожить всех злых существ. Если всех существ убить невозможно, выведите  - 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
Выходные данные
23
Входные данные
3 2
2 1 2 5
2 2 3 5
Выходные данные
-1
Примечание

В первом примере есть 4 способа убить всех существ: (заклинания 1 и 2 – 28 ед. энергии), (1,3,4 – 23), (2,5,6 – 33), (3,4,5,6 – 28). Лучше всего воспользоваться заклинаниями 1,3 и 4.

Во втором примере любое из заклинаний убивает существо 2. Поэтому применить можно только одно из них, но этого будет недостаточно.