İnvestisiyalar Ledi#9091
Ledi investor olmağa qərar verib. O, k şirkətə l qrivna investisiya etməyi planlaşdırır. Ledi vətənpərvərdir, buna görə də yalnız öz ölkəsinin şirkətlərinə investisiya edir. Ölkədə n şəhər var və bu şəhərlər m yollarla birləşdirilib. Hər bir şəhərdən digər bütün şəhərlərə yollarla çatmaq mümkündür. 2^n−1 şirkət mövcuddur. Şəhərlərin hər bir boş olmayan çoxluğu üçün bu çoxluqdakı hər bir şəhərdə ofisi olan bir şirkət mövcuddur.
Ölkədə vəziyyət qeyri-sabitdir, lakin Ledi ağıllıdır, ona görə də yalnız aşağıdakı şərt yerinə yetirildikdə şirkətə investisiya edir: hər hansı bir şəhər bloklandıqda belə, digər bütün ofislər yollarla birləşdirilmiş olmalıdır. İnvestisiya edilən şirkətin ən azı bir ofisi olan hər bir şəhər i, pi qrivna gəlir gətirir. Ledi k şirkətdən daha azına investisiya edə bilər. Beləliklə, əgər o, x şirkətə investisiya edərsə, əlavə olaraq (k − x) · l qrivna gəlir əldə edəcək. Lediyə maksimum gəliri tapmaqda kömək edin.
Birinci sətir n, m, k, l (1 ≤ n ≤ 100 000, n − 1 ≤ m ≤ 300 000, 1 ≤ k ≤ 40, 1 ≤ l ≤ 1 000 000 000) — şəhərlərin sayı, yolların sayı, Ledinin investisiya etməyi planlaşdırdığı şirkətlərin sayı və Ledinin bir şirkətə investisiya etdiyi qrivna miqdarı olan dörd tam ədədi ehtiva edir.
İkinci sətir n tam ədəd p[1], p[2], . . . , p[n] (1 ≤ p[i] ≤ 1 000 000 000) — i-ci şəhərin gəliri ehtiva edir.
Növbəti m sətir hər biri iki tam ədəd u, v (1 ≤ u ≠ v ≤ n) ehtiva edir — aralarında yol olan şəhərlərin nömrələri. Zəmanət verilir ki, şəhər cütü arasında maksimum bir yol ola bilər. Zəmanət verilir ki, bu yollarla hər bir şəhərdən digərinə keçmək mümkündür.
Yeganə sətirdə məsələnin cavabını verin.
Birinci nümunədə ən yaxşı variant 3, 7, 8 şəhərlərində ofisləri olan şirkətə və 1, 5, 6 şəhərlərində ofisləri olan şirkətə investisiya etməkdir.
İkinci nümunədə ən yaxşı variant 1, 2, 3 şəhərlərində ofisləri olan şirkətə və 3, 4, 5 şəhərlərində ofisləri olan şirkətə investisiya etməkdir. Və üçüncü şirkətə investisiya edilməyən l qrivnanı saxlamaqdır.
Nümunə 1
Nümunə 2