RCC 2014 Warmup (Div. 2) |
---|
Закончено |
Мальчик Гена очень хочет попасть на финал «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
Название |
---|