Алkimya
Məlumdur ki, K növ maddə və N növ alkimya reaksiyası mövcuddur. Hər bir reaksiya, müəyyən giriş maddələrindən çıxış maddələri yaradır və hər bir reaksiyanın baş verməsi üçün sabit bir vaxt tələb olunur. Reaksiyalar nəticəsində əldə edilən maddələr təmiz şəkildə ayrılıb, ayrıca istifadə edilə bilər. Hər bir maddə istənilən qədər mövcuddur. Yeni tamamlanmış reaksiyadan əldə edilən maddə dərhal digər reaksiyalarda istifadə oluna bilər. Reaksiyalar eyni zamanda baş verə bilər.
ALCHEMY proqramını yazın ki, verilmiş maddələr və reaksiyalar əsasında, müəyyən bir maddəni əldə etmək üçün lazım olan minimum vaxtı təyin etsin.
Giriş verilənləri
Giriş faylının ilk sətiri dörd tam ədəd ehtiva edir: K (3 ≤ K ≤ 250) — maddələrin sayı, N (3 ≤ N ≤ 500) — reaksiyaların sayı, M (1 ≤ M < K) — əvvəlcədən mövcud olan maddələrin sayı və son maddənin nömrəsi.
Daha sonra N blok gəlir ki, bu bloklar reaksiyaları təsvir edir. Hər bir blok üç sətirdən ibarətdir: birinci sətir reaksiyanın keçirilməsi üçün lazım olan vaxtı göstərən təbii ədəd, ikinci sətir reaksiyaya daxil olan maddələrin sayı və bu maddələrin siyahısı, üçüncü sətir reaksiyanın nəticəsində yaranan maddələrin sayı və onların siyahısı.
Əvvəlcədən mövcud olan maddələr 1 ilə M arasında nömrələnir, digər maddələr isə M+1 ilə K arasında nömrələnir. Bütün reaksiyaların keçirilmə vaxtının cəmi 2∙10^9-u keçmir.
Çıxış verilənləri
Çıxış faylının yeganə sətiri tam ədəd olmalıdır — son maddənin əldə edilə biləcəyi minimum vaxt.
Əgər son maddəni əldə etmək mümkün deyilsə, çıxış faylının yeganə sətiri -1 ədədini ehtiva etməlidir.
Verilmiş giriş nümunəsi üçün, son maddə 4 əldə edilə bilər, əgər ilk üç vaxt vahidi ərzində 2 reaksiyası keçirilərsə və bundan sonra iki vaxt vahidi ərzində 3 reaksiyası keçirilərsə. Beləliklə, 5 vaxt vahidi ərzində lazım olan maddə əldə ediləcək.