Baltic Olympiad in Informatics 2018 Open - practice session

Start

2018-04-27 15:30 UTC

Baltic Olympiad in Informatics 2018 Open - practice session

End

2018-04-27 17:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -590 days 7:44:53

Time elapsed

2:00:00

Time remaining

0:00:00

Problem B
Ссылки

Грейс собирается прочитать некую научную книгу. Она привыкла всегда читать все книги-первоисточники, на которые ссылается изначальная книга, а затем на первоисточники, на которые ссылались они, и так далее. Из-за этого она обычно в итоге читает очень много книг вдобавок к той, которую хотела прочесть изначально.

Библиотекари постоянно жалуются на то, что Грейс берет в библиотеке слишком много книг. Чтобы их поменьше расстраивать, Грейс хочет найти порядок прочтения книг, при котором суммарное время удержания книг дома было бы наименьшим.

Всего Грейс необходимо прочитать $N$ разных книг. Книги пронумерованы от $1$ до $N$, а на прочтение книги $i$ уходит $K_ i$ минут. Каждая книга $i$ содержит список ссылок, состоящий из $F_ i$ книг. Книга, которую Грейс собиралась прочитать изначально, имеет номер $1$. Прежде чем начать читать книгу номер $1$, Грейс взяла из библиотеки все $N$ книг на дом.

Процесс прочтения каждой книги у Грейс проходит следующим образом:

  • Сначала она открывает книгу и сразу же читает список ссылок. Это занимает у неё одну минуту.

  • Затем она прочитывает все книги в списке ссылок, в любом порядке на её усмотрение.

  • После этого она читает саму книгу, и возвращает её в библиотеку. Это занимает ещё $K_ i$ минут.

Вам необходимо найти наименьшую возможную сумму времен хранения всех книг дома, при условии что Грейс будет читать их в оптимальном порядке. Книги могут иметь пустые списки ссылок. Каждая книга, кроме книги номер $1$ присутствует ровно в одном списке ссылок. Также известно, что ссылки не образуют циклов.

Ввод

На первой строке ввода дано целое число $N$ ($1 \le N \le 100\, 000$). Далее следут $N$ строк, по одной на каждую книгу от $1$ до $N$. На каждой из этих строк дано целое число $K_ i$ ($1 \le K_ i \le 1\, 000$) – количество минут, необходимое для прочтения книги. Затем дано целое число $F_ i$ ($0 \le F_ i < N$), за которым следуют $F_ i$ целых чисел – номера книг, на которые ссылается книга $i$.

Вывод

Вывести одно целое число – минимальное суммарное время удержания всех книг.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Группа

Очки

Ограничения

1

20

$1 \le N \le 10, 1 \le K_ i \le 1000$

2

30

$1 \le N \le 50, 1 \le K_ i \le 10$, $F_ i \le 5$

3

20

$1 \le N \le 100\, 000, 1 \le K_ i \le 1000, F_ i \le 5$

4

30

$1 \le N \le 100\, 000, 1 \le K_ i \le 1000$

Объяснение примера 1

минута 1: открыть книгу 1
минута 2: открыть книгу 2
минута 3: открыть книгу 4
минута 4: закрыть книгу 4 (время удержания – 4 минуты)
минута 14: закрыть книгу 2 (время удержания – 14 минут)
минута 15: открыть книгу 3
минута 16: открыть книгу 5
минута 17: закрыть книгу 5 (время удержания – 17 минут)
минута 37: закрыть книгу 3 (время удержания – 37 минут)
минута 38: закрыть книгу 1 (время удержания – 38 минут)

Пример ввода 1 Пример вывода 1
5
1 2 2 3
10 1 4
20 1 5
1 0
1 0
110