Деталі#4851

Деталі

1 секунда

128 мегабайтів

Легка

Підприємство Авто-2012 випускає двигуни для відомих у світі автомобілів. Двигун складається рівно з $n$ деталей, пронумерованих від $1$ до $n$ , причому деталь з номером $i$ виготовляється за $p_{i}$ p_i секунд. Особливістю підприємства Авто-2012 є те, що одночасно може виготовлятися лише одна деталь двигуна. Для виробництва деяких деталей необхідно мати попередньо виготовлений набір інших деталей.

Генеральний директор Авто-2012 поставив перед підприємством амбітне завдання: виготовити деталь з номером $1$ у найкоротший термін, щоб представити її на виставці.

Напишіть програму, яка за заданими залежностями порядку виробництва між деталями знаходить найменший час, за який можна виготовити деталь з номером $1$ .

Вхідні дані

Перший рядок містить $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5) натуральних чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n, які визначають час виготовлення кожної деталі у секундах.

Кожен з наступних $n$ рядків описує характеристики виробничого процесу для кожної деталі. $i$ -ий рядок містить список деталей, які потрібні для виробництва деталі з номером $i$ . У списку немає повторюваних номерів деталей. Список також може бути порожнім — тоді це буде порожній рядок. Сума довжин всіх списків не перевищує $200000$ .

Відомо, що у виробництві деталей не існує циклічних залежностей.

Вихідні дані

Виведіть мінімальний час (у секундах), необхідний для найшвидшого виробництва деталі з номером $1$ .

Приклади

Input	Output
4 8 8 7<br>2 3<br>4<br><br>	19

Приклад 1

Приклад 2

Примітка

Для прикладу оптимальний шлях:

Виготовити деталі $4$ , $2$ та $3$ одну за одною.
Потім виготовити деталь $1$ .

Загальний час $7 + 8 + 8 + 4 = 27$ 7 + 8 + 8 + 4 = 27, але оскільки деталі $2$ і $3$ можуть бути виготовлені паралельно після виготовлення деталі $4$ , необхідно враховувати найтриваліший ланцюжок — $7 + 8 + 4 = 19$ 7 + 8 + 4 = 19.