Корупція
Корупція
В міністерстві, що видає ліцензії, працює N чиновників (включаючи міністра), причому:
кожен чиновник (крім міністра) має одного начальника;
кожен чиновник має від 0 до 4 підлеглих чиновників;
начальник мого начальника, не мій начальник;
підлеглий мого підлеглого, не мій підлеглий.
Ліцензію підписує міністр. Щоб мати підпис будь-якого чиновника або міністра, потрібно дати йому хабара, попередньо отримавши підпис одного з його підлеглих, якщо вони є.
Якої найменшої суми достатньо для отримання ліцензії?
Вхідні дані
У першому рядку число N – кількість чиновників в міністерстві. Далі йдуть N рядків. В і-му рядку (і = 1..N) записано дані про і-го чиновника в такому форматі: D[і] - сума хабара, K[і] – кількість та номери його підлеглих. Міністр має номер один. Усі числа натуральні, не перевищують 100.
Вихідні дані
Відповідь до задачі.
Приклад
7 40 3 2 3 4 60 1 5 45 2 6 7 75 0 20 0 15 0 25 0
100