Qarışıq Uçuş Planları#6994
Ad Hoc Poçt Şirkəti (AHPC) poçt zərflərini çatdırmaq üçün sadə bir strategiyaya malikdir: O, könüllü axtarır və ona başlanğıc şəhərdən təyinat şəhərinə ən ucuz uçuş planını alır və könüllüyə başlanğıc hava limanında bir çanta zərf verir ki, onları təyinat hava limanında şirkətin müxbirinə təhvil versin.
İki hava limanı arasında birbaşa uçuşlara əlavə olaraq, bir neçə fərqli aralıq hava limanında dayanacaqları olan dolayı səfərlər də mövcuddur. Dolayı səfər sərnişini həmişə birinci hava limanından başlamalı və aralıq hava limanlarını ardıcıl olaraq ziyarət etməlidir (dolayı səfər cədvəlinə uyğun olaraq, arada başqa birbaşa uçuşlar və ya dolayı səfərlər istifadə etmədən), lakin dolayı səfərin qalan hissəsini istənilən aralıq hava limanında tərk edə bilər. Dolayı səfərin qiyməti sabitdir; sərnişin bütün uçuşlardan istifadə etsə də, ortada dayandırsa da fərq etməz. Uçuş planı bir neçə birbaşa uçuşlardan və dolayı səfərlərin tam və ya qismən hissələrindən ibarət ola bilər.
İqtisadiyyat naminə, AHPC qarışıq uçuş planlarından istifadə etməyə çalışır: tutaq ki, bir neçə çanta var, biri A hava limanından B hava limanına, digəri isə C hava limanından D hava limanına çatdırılmalıdır (A, B, C, D fərqli hava limanlarıdır). Şirkət birinci könüllü üçün A hava limanından D hava limanına və ikinci könüllü üçün C hava limanından B hava limanına iki uçuş planı ala bilər ki, bu iki plan eyni hava limanı M (bu 4 hava limanından fərqli olmaya bilər) ilə paylaşsın və burada iki könüllü görüşüb çantalarını dəyişdirsinlər. Beləliklə, AHPC hər çantanın düzgün təyinat yerinə çatdırılmasını təmin edir, eyni zamanda ümumi qiymət azaldıla bilər.
Məsələn, yuxarıdakı şəkildə altı hava limanı ilə birbaşa uçuşlar (bərk oxlar), dolayı səfərlər (kəsik və nöqtəli oxlar) və onların qiymətləri təsvir edilmişdir. İki çanta göndərilməlidir, biri 3 (A) hava limanından 5 (B) hava limanına, digəri isə 6 (C) hava limanından 1 (D) hava limanına. Şirkət birinci könüllü üçün (3, 4), (4, 5) uçuş planını və ikinci könüllü üçün (6, 5), (5, 1) uçuş planını ümumi 300 qiymətinə ala bilər. Lakin daha ucuz alternativ (3, 4, 1, 2, 6) birinci könüllü üçün və (6, 2), (2, 4, 5) ikinci könüllü üçün, ümumi 250 qiymətinə mövcuddur. Könüllülər 4 (M) hava limanında görüşüb çantalarını dəyişdirirlər və birinci könüllü dolayı səfəri 1 hava limanında tərk edəcək.
Verilən uçuş məlumatlarına əsasən, çantaların çatdırılması üçün ən iqtisadi qiyməti tapan bir proqram yazmalısınız.
Girişdə bir neçə hal var. Hər bir halın ilk sətri altı tam ədəd n, m, A, B, C və D ehtiva edir, burada n (4 ≤ n ≤ 100) hava limanlarının sayıdır və m (0 ≤ m ≤ 10000) birbaşa uçuşlar və dolayı səfərlərin ümumi sayıdır, bunlardan ən çox 1000 dolayı səfərlərdir. Növbəti m sətirdən hər biri i-ci sətir iki müsbət tam ədəd p_i (qiymət, p_i ≤ 10^6) və s_i (birbaşa uçuş üçün 1 və dolayı səfər üçün daha çox) ilə başlayır, ardınca s_i+1 fərqli hava limanı nömrələri gəlir ki, bu da i-ci birbaşa uçuş/dolayı səfərdə ziyarət edilən hava limanlarının sırasını göstərir.
Giriş "0 0 0 0 0 0" ilə bitir ki, bu da işlənməməlidir.
Hər bir test halı üçün ən ucuz uçuş planının ümumi qiymətini bir sətirdə çıxarın və ya ən azı bir çantanın çatdırılması mümkün deyilsə "Impossible!" (tırnaqsız) çıxarın.
Nümunə 1