Gümüş uğrunda döyüş#7014
Piter Heyn, Səksən illik müharibə zamanı Hollandiya Birləşmiş Əyalətləri ilə İspaniya arasında xidmət etmiş hollandiyalı dəniz zabiti idi. Onun ən məşhur qələbəsi 1628-ci ildə Kuba yaxınlığında "Zilvervloot" ("Gümüş donanması") ələ keçirməsi idi. Burada o, İspaniyanın Şimali və Cənubi Amerikadakı koloniyalarından İspaniyaya gümüş daşıyan bir sıra ispan gəmilərini ələ keçirdi. Bu məşhur dəniz döyüşü haqqında məlumatlar qismən məlumdur, buna görə də aşağıda verilən təsvir bəzi tarixi qeyri-dəqiqliklər ehtiva edə bilər.
Gümüş donanması gümüş sikkələr daşıyan gəmilərdən ibarət idi. Piter Heynin əsas strategiyası sadə idi: donanmadan bir neçə gəmini ayıraraq onların içindəkiləri ələ keçirmək.
Hollandiyalıların bu planı həyata keçirməsinə mane olmaq üçün ispanlar donanmalarındakı bütün gəmiləri böyük dəmir zəncirlərdən istifadə edərək birləşdirdilər. Donanmadakı hər bir gəmi ən azı bir başqa gəmi ilə birləşdirilmişdi. İstənilən iki gəmi bir zəncirdən çox olmamaqla birləşdirilmişdi. İspanlar zəncirlərin kəsişmədiyinə əmin oldular, əks halda onlar düyünlənə bilərdi. Nəticədə, gəmilər və zəncirlər əlaqəli düz qrafik meydana gətirdi.
Bununla belə, ispanların qabaqlayıcı tədbirləri yalnız vəziyyətlərini pisləşdirdi. Təcrübəli dəniz zabiti kimi, Piter Heyn bilirdi ki, hər iki gəmi bir zəncirlə birləşdirildikdə bir qrup gəmini yedəkləmək ən asandır. O, belə qrupları zəncir qrupları adlandırdı.
Piter Heyn, ispan donanmasının qalan gəmiləri ilə əlaqələrini bir neçə dəqiq top atəşi ilə kəsdikdən sonra, ən çox qənimət olan qrupu yedəkləməyi əmr etdi. Zəncir qrupundakı ümumi qənimət, onu təşkil edən gəmilərdəki ümumi gümüş sikkələrin miqdarıdır.
Gümüş donanması qrafik şəklində təqdim olunur: hər bir nöqtə donanmadakı bir gəmini, hər bir xətt isə iki gəmini birləşdirən zənciri göstərir. Şəkildə kəsik xətlərlə birləşdirilmiş gəmilər, ən böyük ümumi gümüş sikkə dəyərini təmin edən qrupa uyğundur. Bu halda, Piter Heyn donanmadan 4500 gümüş sikkə ələ keçirir.
Gümüş donanmasının təsviri ilə, ən çox qənimət olan qrupun dəyərini tapın (yəni qrupa daxil olan gəmilərdəki ümumi gümüş sikkələrin miqdarı).
Hər bir test üçün:
Sətir iki tam ədəd v (2 ≤ v ≤ 450) və e (1 ≤ e ≤ 900) - donanmadakı gəmi sayı və zəncir sayı ehtiva edir.
Növbəti v sətir S[1], S[2], ..., S[v] - i nömrəli gəminin daşıdığı gümüş sikkələrin miqdarını (1 ≤ i ≤ v) göstərir. S[i] ədədləri təbii ədədlərdir və 100 ≤ S[i] ≤ 6000.
Daha sonra hər bir zəncir üçün iki tam ədəd c[start] və c[end] - zəncirlə birləşdirilmiş gəmilərin nömrələri (1 ≤ c[start] < c[end] ≤ v) verilir.
Hər bir donanma əlaqəli düz qrafik meydana gətirir.
Hər bir test üçün Piter Heynin donanmadan ələ keçirdiyi gümüş sikkələrin miqdarını ayrı-ayrı sətirdə çıxarın.
Nümunə 1