Siz ACM ICPC-nin bağlanış mərasimi üçün konfrans zalını hazırlamaqdan məsulsunuz. Köhnə zal üçün zərif bir bəzək hazırlamaq məqsədilə mükəmməllikçi bir sentimental otaq dizaynerini işə götürmüsünüz. Mərasim bir neçə saatdan sonra başlayacaq və dizayner bəzəyin tamamlandığını sizə yeni xəbər verib. Konfrans zalına çatdığınızda divarda qəribə bir sxemlə qarşılaşırsınız. Dizayner sizə həyatın və ACM ICPC-nin mənalarını sxemin hər bir parçasının altında izah etməyə başlayır. Sxem LED-lərdən (İşıq Yayan Diodlar) və birləşmələr və tellərlə birləşdirilmişdir. Siz LED-lərin yandırılıb-yandırılmaması lazım olduğunu soruşursunuz. "Əlbəttə!" dizayner cavab verir, "Hər bir LED yanmalıdır, əks halda bütün iş zibilə çevrilir!" Siz sxemin ətrafına baxaraq onun enerji prizini axtarırsınız.
- Enerji prizi haradadır?
- Hə? Bu mənim işimin çərçivəsindən kənardadır! LED-lərə elektrik enerjisini təmin etmək sizin işinizdir. Və diqqətli olun! Sxemin heç bir hissəsini çıxarmayın və ya dəyişdirməyin; Sadəcə enerji təchizat kabellərini birləşmələrə qoşun. Mən indi getməliyəm. Mən mükəmməl işimin hesabatını menecerinizə göndərəcəyəm. Sağ olun.
Qəribə sxemlə tək qaldığınızda, sxemi yoxlamağa başlayırsınız.
İncandescent lampalardan fərqli olaraq, hansı ki, elektrik polaritesindən asılı olmayaraq işıq yayır, LED-lər yalnız düzgün elektrik polaritesi ilə işıq yayır (yəni, onların anod pimi katod pimindən daha yüksək elektrik potensialına malik olduqda). Hər LED-in minimum gərginliyi var. LED (düzgün polarite ilə olsa belə) piminin elektrik potensial fərqi onun minimum gərginliyindən az olduqda işıq yaymır. Hər LED-in həmçinin maksimum gərginliyi var. LED-in elektrik potensial fərqi onun maksimum gərginliyini aşdıqda LED məhv olur.
Sxem üzərindəki yoxlamanız göstərir ki, o, üç növ komponentdən ibarətdir:
LED-lər: Xoşbəxtlikdən, sxemin bütün LED-ləri eyni növdəndir və beləliklə eyni minimum gərginliyə və eyni maksimum gərginliyə malikdirlər.
Birləşmələr: Sxemdəki LED-in hər iki pimi bir birləşməyə qoşulub. Birləşmələr yalnız LED pimlərinin birləşdirilməsi üçün deyil, həm də tel uclarının birləşdirilməsi üçün istifadə olunur.
Tellər: Hər telin iki ucu var və bir birləşməni birbaşa başqa bir birləşməyə birləşdirir, onları eyni elektrik potensialına məcbur edir.
Hər birləşməyə müxtəlif gərginlik dəyərlərinə malik xarici elektrik dirəkləri qoşaraq, birləşmələrə müxtəlif elektrik potensialları daxil edə bilərsiniz. Qeyd edin ki, hər birləşmə xarici elektrik dirəyinə qoşulmalıdır. Qısa dövrələrdən ehtiyatlı olun: hər telin ucları eyni elektrik potensialına malik olmalıdır. Ən az elektrik potensialının sıfır olduğunu fərz edə bilərik. Beləliklə, bütün elektrik potensialları qeyri-mənfi hesab edilə bilər.
İndi sizə tələb olunan elektrik dirəklərini təmin edən xarici enerji təchizatı almaq lazımdır. Belə enerji təchizatlarının dəyəri onların yuxarı həddi: təmin etdikləri maksimum gərginlikdən asılıdır.
LED sxeminin spesifikasiyası verildikdə, bütün LED-lərin düzgün (qısa dövrələrsiz və LED məhvi olmadan) işıqlandırılmasının mümkün olub-olmadığını yoxlayan bir proqram yazmalısınız. Əgər mümkünlük varsa, proqram həmçinin bütün LED-lərin işıq yaya biləcəyi minimum mümkün enerji təchizatı yuxarı həddini də hesablamalıdır.
Giriş bir neçə test halından ibarətdir. Hər test halı bir LED sxemini təsvir edir və 5 boşluqla ayrılmış tam ədədlə başlayır: J, L, W, m və M, burada J birləşmələrin sayı (2 ≤ J ≤ 500), L LED-lərin sayı (1 ≤ L ≤ 5000), W tellərin sayı (0 ≤ W ≤ 5000), və m və M LED-lərin minimum və maksimum gərginliyidir (1 ≤ m < M ≤ 1000). Birləşmələrin 1 ilə J arasında nömrələndiyini fərz edin.
Növbəti L sətirdən hər biri iki boşluqla ayrılmış tam ədəd ilə bir LED-i təmsil edir. Birinci tam ədəd LED-in anod pimini birləşdirən birləşmənin nömrəsidir və ikinci tam ədəd katod piminin nömrəsidir. Sonra, W sətir gəlir, hər biri sxemin bir telini təsvir edir və iki boşluqla ayrılmış tam ədəd: telin birbaşa birləşdirdiyi birləşmələr.
Giriş "0 0 0 0 0" (sitatlar olmadan) sətiri ilə bitir.
Hər test halı üçün bir sətir çıxış yazın. Əgər həmin test halının sxemində bütün LED-ləri düzgün işıqlandırmaq mümkün deyilsə, yalnız "Impossible" sözünü yazın (sitatlar olmadan). Əks halda, bütün LED-lərin işıqlandırıla biləcəyi minimum enerji təchizatı yuxarı həddini göstərən bir tam ədəd yazın.
Nümunə 1