Известны K видов веществ и N типов
алхимических реакций. Каждая реакция по набору входных веществ
продуцирует набор выходных. Проведение каждой реакции требует
фиксированного времени. Любые вещества, полученные в
результате реакций, можно выделять в чистом виде для
отдельного использования. Каждого вещества всегда достаточно
для любого использования. Вещество, полученное в результате
только что закончившейся реакции, можно сразу же использовать
в других реакциях. Реакции могут проходить одновременно.
Задание
Напишите программу ALCHEMY, которая по информации
об известных веществах и реакциях определяет за какое
наименьшее время можно получить целевое вещество.
Входные данные
Первая строка входного файла ALCHEMY.DAT содержит
четыре целых числа: K (3£K£250) — количество веществ,
N (3£N£500) — количество реакций,
M (1£M<K) —
количество имеющихся сначала веществ, а также номер целевого
вещества.
Далее следуют N блоков, которые описывают
реакции. Каждый блок состоит из трех строк: первая содержит
натуральное число — время, необходимое для проведения реакции,
вторая строка — количество веществ, которые вступают в
реакцию, и перечень этих веществ, третья строка — количество
веществ, которые образовываются в результате реакции, и их
перечень.
Вещества, имеющиеся сначала, имеют номера от 1 до
M, а все остальные — от M+1 до K. Сумма
времен проведения всех реакций не превышает
2*109.
Выходные данные
Единственная строка выходного файла ALCHEMY.SOL
должна содержать целое число — найденное минимальное время, за
которое может быть получено целевое вещество.
Если получить целевое вещество невозможно,
единственная строка выходного файла должна содержать число
-1.
Для приведенного примера входных данных, целевое
вещество 4 можно получить, если на протяжении первых трех
единиц времени провести реакцию 2, а после этого на протяжении
двух единиц времени провести реакцию 3. Таким образом, за 5
единиц времени будет получено требуемое вещество.
Пример входных данных
4 3 1 4
8
1 1
1 4
3
1 1
2 2
3
2
2 1 3
1 4
Пример выходных данных