Şəbəkənin sındırılması#5180
Pentaqonun kompüter şəbəkəsi kompüterdən ibarətdir və bəziləri birbaşa ikitərəfli əlaqə kanalları ilə birləşdirilir. Şəbəkənin təhlükəsizliyini artırmaq üçün bu əlaqə kanallarının sayı minimuma endirilib ki, istənilən iki kompüter birbaşa və ya digər kompüterlər vasitəsilə əlaqə qura bilsin.
Mərkəzi Araşdırmalar Bürosu şəbəkədə ötürülən bütün mesajları izləmək istəyir. Bunun üçün proqramçılar bir virus hazırlayıblar ki, bu virus hər hansı bir kompüterə quraşdırıldıqda, oradan keçən bütün məlumatları Mərkəzi Araşdırmalar Bürosuna ötürür. Virusun müxtəlif kompüterlərə quraşdırılması üçün tələb olunan xərc fərqli ola bilər. Sizin tapşırığınız — bütün məlumatların izlənə biləcəyi və ümumi xərclərin minimum olacağı kompüterlər toplusunu seçməkdir.
İlk sətirdə şəbəkədəki kompüterlərin sayı olan (1 \leq N \leq 500) verilir.
Növbəti sətirin hər birində, -ci sətrdə, -ci kompüter ilə birbaşa əlaqədə olan kompüterlərin nömrələri göstərilib.
Sonuncu sətirdə tam ədəd verilir: hər biri aralığında olmaqla, -ci ədəd virusun -ci kompüterə quraşdırılması üçün lazım olan xərci göstərir.
Virusun quraşdırılması üçün mümkün olan minimal ümumi xərci çap edin.
Nümunə 1