eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Корупція

Корупція

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

В міністерстві, що видає ліцензії, працює N чиновників (включаючи міністра), причому:

  • кожен чиновник (крім міністра) має одного начальника;

  • кожен чиновник має від 0 до 4 підлеглих чиновників;

  • начальник мого начальника, не мій начальник;

  • підлеглий мого підлеглого, не мій підлеглий.

Ліцензію підписує міністр. Щоб мати підпис будь-якого чиновника або міністра, потрібно дати йому хабара, попередньо отримавши підпис одного з його підлеглих, якщо вони є.

Якої найменшої суми достатньо для отримання ліцензії?

Вхідні дані

У першому рядку число N – кількість чиновників в міністерстві. Далі йдуть N рядків. В і-му рядку (і = 1..N) записано дані про і-го чиновника в такому форматі: D[і] - сума хабара, K[і] – кількість та номери його підлеглих. Міністр має номер один. Усі числа натуральні, не перевищують 100.

Вихідні дані

Відповідь до задачі.

Приклад

Вхідні дані #1
7
40 3 2 3 4 
60 1 5 
45 2 6 7 
75 0 
20 0 
15 0 
25 0
Вихідні дані #1
100