Деталі
Підприємство "Авто-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.
