Злам мережі#5180
Комп'ютерна мережа Пентагону складається з комп'ютерів, деякі з яких безпосередньо з'єднані двосторонніми каналами зв'язку. Для підвищення безпеки кількість таких каналів зведено до мінімуму за умови, що будь-які два комп'ютери можуть обмінюватися інформацією або безпосередньо, або через інші комп'ютери мережі.
Центральне бюро розслідувань прагне перехоплювати всі повідомлення, що передаються мережею Пентагону. З цією метою розроблено вірус, який, перебуваючи на певному комп'ютері, передає всю інформацію, що через нього проходить, у Центральне бюро розслідувань. Вартість встановлення вірусу може відрізнятися для різних комп'ютерів. Ваше завдання — визначити такий набір комп'ютерів для зараження, щоб усі повідомлення можна було перехопити, а сумарні витрати були мінімальними.
У першому рядку міститься одне ціле число (1 \leq N \leq 500) — кількість комп'ютерів у мережі.
У наступних рядках -й рядок містить номери комп'ютерів, які безпосередньо з'єднані з комп'ютером .
У останньому рядку дано цілих чисел у діапазоні — -те число — це вартість встановлення вірусу на -й комп'ютер.
Виведіть мінімально можливу суму витрат на встановлення вірусу.
Приклад 1