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