Предприятие "Авто-2012" выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p[i]
секунд. Специфика предприятия "Авто-2012" заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.
Генеральный директор "Авто-2012" поставил перед предприятием амбициозную задачу - за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.
Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.
Первая строка содержит n (1 ≤ n ≤ 10^5
) натуральных чисел p[1]
, p[2]
, ..., p[n]
, определяющих время изготовления каждой детали в секундах.
Каждая из следующих n строк описывает характеристики производства деталей. Здесь i-ая строка содержит список деталей, которые требуются для производства детали с номером i. В списке нет повторяющихся номеров деталей. Список может быть в том числе пустым - тогда ему будет соответствовать пустая строка! Сумма длин всех списков не превосходит 200000.
Известно, что не существует циклических зависимостей в производстве деталей.
Вывести минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1.