Алхімія
Відомі K видів речовин та N типів алхімічних реакцій. Кожна реакція за набором вхідних речовин продуктує набір вихідних. Проведення кожної реакції вимагає фіксованого часу. Довільні речовини, отримані в результаті реакцій, можна виділяти у чистому вигляді для окремого використання. Кожної речовини завжди достатньо для довільного використання. Речовину, отриману в результаті реакції, що тільки що завершилась, можна відразу ж використовувати у інших реакціях. Реакції можуть проходити одночасно.
Напишіть програму ALCHEMY, яка за інформацією про відомі речовини та реакції визначає за який найменший час можна оримати задану речовину.
Вхідні дані
Перший рядок вхідного файлу містить чотири цілих числа: K (3 ≤ K ≤ 250) — кількість речовин, N (3 ≤ N ≤ 500) — кількість реакцій, M (1 ≤ M < K) — кількість наявних спочатку речовин, а також номер кінцевої речовини.
Далі йде N блоків, які описують реакції. Кожен блок складається з трьох рядків: перший містить натуральне число — час, необхідний для проведення реакції, другий рядок — кількість речовин, які вступають у реакцію, та перелік цих речовин, третій рядок — кількість речовин, які утворюються у результаті реакції, та їх перелік.
Речовини, шо є спочатку, мають номери від 1 до M, а усі інші — від M+1 до K. Сума часу проведення усіх реакцій не перевищує 2∙10^9.
Вихідні дані
Єдиний рядок вихідного файлу повинен містити ціле число — знайдений мінімальний час, за який може бути отримана кінцева речовина.
Якщо отримати кінцеву речовину неможливо, єдиний рядок вихідного файлу повинен містити число -1.
Для наведеного приклада вхідних даних, кінцеву речовину 4 можна отримати, якщо на протязі перших трьох одиниць часу провести реакцію 2, а після цього на протязі двох одиниць часу провести реакцію 3. Таким чином, за 5 одиниць часу буде отримана порібна речовина.