D. Хитрый Гена
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Гена очень хочет попасть на финал «Russian Code Cup», ну или хотя бы получить футболку. Но предлагаемые на отборочном раунде задачи слишком сложные, поэтому он договорился с n друзьями, что они решат задачи за него.

Участникам на отборочном раунде предлагают m задач. Про каждого своего друга Гена знает, какие задачи он умеет решать. Но друзья не согласны помогать Гене просто так: i-й друг требует за свою помощь в решении всех задач, которые он может решить, xi рублей, более того, он согласен писать код по задачам, только если к компьютеру Гены подключено не менее ki мониторов, а каждый монитор стоит b рублей.

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

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

В первой строке записаны три целых числа n, m и b (1 ≤ n ≤ 100; 1 ≤ m ≤ 20; 1 ≤ b ≤ 109) — количество друзей Гены, количество задач и стоимость одного монитора.

В следующих 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, если этого нельзя добиться.

Примеры
Входные данные
2 2 1
100 1 1
2
100 2 1
1
Выходные данные
202
Входные данные
3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2
Выходные данные
205
Входные данные
1 2 1
1 1 1
1
Выходные данные
-1