История №264355

Задача по информатике на всероссийском конкурсе по програмированию,
проводимом Фихтехом. Для сомневающихся- ссылка
http://frtk.ru/it2007/tasksa.html
Слов нет...................

А2. Коррумпированное государство

В тридевятом царстве в тридесятом государстве для получения лицензии на
проведение любых исследований необходимо разрешение председателя
Комиссии по наукоемким технологиям. В комиссии N < =100 чиновников.
Соответственно, у каждого чиновника (кроме самого главного №1) есть 1
непосредственный начальник и могут быть подчиненные (как
непосредственные, так и подчиненные его подчиненных). Согласно
естественным правилам бюрократической системы каждый чиновник, кроме
самых младших, на заявлении может потребовать на заявлении подписи
одного или нескольких своих прямых подчиненных и взятку, как за то,
чтобы можно было обойти нижестоящих чиновников, так и просто за свою
подпись. Для каждого чиновника известен непустой список возможных
наборов "виз" (подписей своих подчиненных) и соответствующая каждому
набору взятка (достаточно наличие только одного набора). Пустой набор
означает, что данный чиновник не требует виз в данном случае. В какую
минимальную сумму обойдется лицензия на проведение исследований?

Ввод: Ν , в следующих строках: < номер чиновника (1..N) > < взятка
— целое число меньше 10000 > < набор виз (может быть пустым) — номера
чиновников, разделенные пробелом > (Замечание: для каждого чиновника
можно записать несколько таких строк). Количество виз в наборе не
превосходит 50. Количество наборов для каждого чиновника не превосходит
15.

Вывод: < Сумма взяток >

Пример

Ввод: 4

3 100

1 300

1 100 2 3

4 20

3 50 4

2 50

1 200 2


Вывод: 220