Alchemy
There are K types of substances and N known alchemical reactions. Each reaction transforms a set of input substances into a set of output substances and requires a fixed amount of time to complete. Any substances produced can be isolated in their pure form for separate use. There is always an unlimited supply of each substance available. A substance produced from a completed reaction can be immediately used in other reactions. Reactions can occur simultaneously.
Write a program, ALCHEMY, that determines the minimum time needed to produce a specified substance, given information about the known substances and reactions.
Input
The first line of the input contains four integers: K (3 ≤ K ≤ 250) — the number of substances, N (3 ≤ N ≤ 500) — the number of reactions, M (1 ≤ M < K) — the number of substances initially available, and the number of the final substance desired.
Following this, there are N blocks describing the reactions. Each block consists of three lines: the first line contains a natural number representing the time required to perform the reaction, the second line lists the number of substances needed for the reaction and the substances themselves, and the third line lists the number of substances produced by the reaction and the substances themselves.
The substances initially available are numbered from 1 to M, while all others are numbered from M+1 to K. The total time required for all reactions does not exceed 2∙10^9.
Output
The output should be a single line containing an integer — the minimum time required to produce the final substance.
If it is impossible to produce the final substance, the output should be -1.
For the provided example input, the final substance 4 can be obtained by performing reaction 2 during the first three units of time, followed by reaction 3 for two units of time. Thus, the desired substance will be produced in 5 units of time.