Офіційне погодження#2996

Умова Обговорення

Офіційне погодження

1 секунда

64 мегабайти

Дуже легка

У відділі, що видає офіційні документи, працює $N$ співробітників (разом із директором), причому:

Кожен співробітник (крім директора) має одного безпосереднього начальника.
Кожен співробітник має від $0$ до $4$ підлеглих.
Начальник мого начальника не є моїм безпосереднім начальником.
Підлеглий мого підлеглого не є моїм безпосереднім підлеглим.

Щоб отримати фінальний підписаний документ, потрібно зібрати послідовність погоджень, починаючи з одного з підлеглих (якщо такі є), а потім відповідного співробітника або директора. Для кожного погодження необхідно сплатити офіційний збір цьому співробітнику.

Який мінімальний загальний офіційний збір потрібно сплатити, щоб отримати фінальний документ у директора?

Вхідні дані

У першому рядку дано число $N$ — кількість співробітників у відділі. Далі йдуть $N$ рядків. У $i$ -му рядку (i = 1, \ldots, N) наведені дані про $i$ -го співробітника: D_i — офіційний внесок, K_i — кількість підлеглих, і їхні номери. Директор має номер $1$ . Усі числа — натуральні, не перевищують $100$ .

Вихідні дані

Виведіть відповідь на задачу.

Приклади

Приклад 1

Loading

Loading

i = 1, \dots, N

D_{i}

K_{i}