Yeni poçt#7378
"Нова пошта" - malların və yüklərin sürətli çatdırılması xidmətidir. "Нова пошта"nın fəaliyyət sahəsi anbarından ibarətdir və bu anbarlar artıq açılmış və lisenziyalaşdırılmış marşrutlarla bir-birinə bağlıdır. Hər bir marşrut yalnız iki anbar arasında mövcuddur və onların uclarında yerləşir.
Şirkətin tam fəaliyyət göstərməsi üçün bir neçə əlavə marşrut açılmalıdır ki, hər hansı iki anbar arasında birbaşa və ya aralıq anbarlar vasitəsilə çatdırılma mümkün olsun. Hər bir anbarında lisenziyanın dəyəri massivində göstərilib. Anbarlar və arasında yeni marşrut açmaq üçün hər iki anbarda lisenziya almaq tələb olunur, yəni bu, C[i]+C[j] məbləğində xərc tələb edir.
"Нова пошта" çatdırılma xidmətinin tam fəaliyyətini təmin etmək üçün hansı minimal məbləğ kifayətdir?
Birinci sətirdə və ədədləri verilir, 0 \leq N \leq 1000, ikinci sətirdə massivinin elementi, 0 \leq C_i \leq 1000000. Sonrakı sətirdə artıq açılmış marşrutları təsvir edən ədədlər cütləri verilib. Bütün ədədi dəyərlər təbiidir.
Məsələnin cavabı.
Nümunə 1