Şəbəkə Planlaşdırılması
Neft pərakəndə satış sənayesində yanacaqdoldurma məntəqələrinin yerləşdiyi yerlər şirkətin mənfəəti üçün çox önəmlidir. Mənfəəti maksimuma çatdırmaq üçün şirkət yeni yanacaqdoldurma məntəqələrinin harada tikiləcəyini müəyyən etmək üçün "Şəbəkə Planlaması" konsepsiyasından istifadə edir.
Siz bu şirkətin məsləhətçisisiniz. Şirkət sizə şəhərlərin sayı və onların necə əlaqəli olduğu, yanacaq tələbatının litrlə miqdarı, artıq yanacaqdoldurma məntəqəsi olan şəhərlərin siyahısı və bu il tikiləcək yeni yanacaqdoldurma məntəqələrinin ümumi sayını əhatə edən məlumatlar təqdim edir.
Onların sizdən istədiyi nəticə "hansı şəhərlərdə yeni yanacaqdoldurma məntəqələri tikməlidirlər ki, mənfəətlərini maksimuma çatdırsınlar"dır. Sadə səslənir, elə deyilmi?
Budur bilmək lazım olanların siyahısı:
Bu ölkədə N şəhər olacaq. Hər şəhər yalnız bir yanacaqdoldurma məntəqəsinə sahib ola bilər.
Hər yanacaqdoldurma məntəqəsinin məhdudiyyətsiz yanacaq tələbatını təmin edə biləcəyini fərz edirik.
Hər yanacaqdoldurma məntəqəsi öz şəhərinin yanacaq tələbatının 70%-ni və qonşu şəhərlərin tələbatının 10%-ni təmin edəcək, qonşu şəhərlərin öz yanacaqdoldurma məntəqəsinin olub-olmamasından asılı olmayaraq.
Məsələn, əgər Şəhər A, Şəhər B və Şəhər C hamısı əlaqəlidirsə; Şəhər A və Şəhər B öz yanacaqdoldurma məntəqələrinə malikdirsə, onda Şəhər A öz yanacaq tələbatının 70%-ni və Şəhər B və Şəhər C-dən 10%-ni təmin edəcək. Şəhər B də eyni şəkildə.
Coğrafi məhdudiyyətlərə görə hər şəhərin üçdən çox qonşu şəhəri olmayacaq.
Son olaraq, onların ümumi gəliri təmin edə bildikləri ümumi yanacaq tələbatının birbaşa dəyişməsidir.
Giriş verilənləri
Girişin ilk sətri test halları sayını T ≤ 10 göstərir.
Hər test halı şəhərlərin sayını N (1 ≤ N ≤ 100000) ilə başlayır.
Sonrakı N sətrləri hər şəhərdəki yanacaq tələbatını göstərən D_i (0 ≤ D_i ≤ 1000) tam ədədi ehtiva edir.
Növbəti sətrdə kənarların sayı olan bir tam ədəd E var.
Sonrakı E sətrləri 2 tam ədəd C_1 və C_2 ehtiva edir, iki tərəfli qonşu şəhərləri təsvir edir. Girişdə təkrarlanan kənarlar olmayacaq (yəni, (C_1, C_2) üçün bir kənar varsa, eyni giriş dəstində (C_2, C_1) üçün kənar olmayacaq). Həmçinin qeyd edin ki, bütün şəhərlər 1 ilə N arasında nömrələnəcək.
Növbəti sətrdə mövcud yanacaqdoldurma məntəqələrinin sayı olan bir tam ədəd S (0 ≤ S < N) var.
Sonrakı S sətrləri artıq yanacaqdoldurma məntəqəsinə sahib olan şəhəri göstərən bir tam ədəd C ehtiva edir.
Son sətrdə bu il tikməli olduqları yeni yanacaqdoldurma məntəqələrinin dəqiq sayını göstərən bir tam ədəd M (1 ≤ M ≤ N–S) var.
Çıxış
Hər test halı üçün iki sətr çıxış edin.
Birinci sətrdə mövcud yanacaqdoldurma məntəqələrindən və optimal şəhərlərdəki yeni yanacaqdoldurma məntəqələrindən təmin edə biləcəkləri maksimum ümumi yanacaq tələbatını (ümumi yuvarlama qaydalarından istifadə edərək) göstərən müsbət tam ədəd çıxış edin.
İkinci sətrdə yeni yanacaqdoldurma məntəqələrini tikməli olduqları optimal şəhərlərin siyahısını, boşluqla ayrılmış və artan sırada verin. Mövcud yanacaqdoldurma məntəqələri olan şəhərlər bu siyahıya daxil edilmir. Əgər bir neçə mümkün həll varsa, leksik sıralamada birinci olanı çıxış edin.
Bu nümunə üçün təsvir
Birinci Nümunə
Bu təsvirə baxaraq görəcəksiniz ki, əgər yalnız Şəhər 3-də yeni yanacaqdoldurma məntəqəsi tikərlərsə, ümumi təminatı 360 litr maksimuma çatdıracaq.
İkinci nümunə
Bu nümunədə iki ən yaxşı həll var. Şəhər 1, şəhər 2 və şəhər 5-də yeni məntəqələr tikmək, şəhər 1, şəhər 3 və şəhər 5-də yeni məntəqələr tikmək qədər mənfəət verəcək. Biz 1 2 5 cavabını verməliyik, çünki leksik sırada birinci görünür. Şəhər 1 üçün ümumi təminat 268.2, şəhər 2 üçün 182.6 və şəhər 5 üçün 290 olacaq. Artıq yanacaqdoldurma məntəqəsi olan şəhər 4 150 litr təmin edir. Ümumi təminat 268.2 + 182.6 + 290 + 150 = 890.8-dir. Bu, 891-ə yuvarlanır.
