eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Детали

Детали

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Предприятие "Авто-2012" выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p[i] секунд. Специфика предприятия "Авто-2012" заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор "Авто-2012" поставил перед предприятием амбициозную задачу - за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.

Входные данные

Первая строка содержит n (1n10^5) натуральных чисел p[1], p[2], ..., p[n], определяющих время изготовления каждой детали в секундах.

Каждая из следующих n строк описывает характеристики производства деталей. Здесь i-ая строка содержит список деталей, которые требуются для производства детали с номером i. В списке нет повторяющихся номеров деталей. Список может быть в том числе пустым - тогда ему будет соответствовать пустая строка! Сумма длин всех списков не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

Выходные данные

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

prb4851.gif

Пример

Входные данные #1
100 200 300
2

2 1
Выходные данные #1
300
Входные данные #2
3 5 1 2
3
1 4
4


Выходные данные #2
6