Підприємство "Авто-2012" випускає двигуни для відомих у всьому світі автомобілів. Двигун складається рівно з n деталей, пронумерованих від 1 до n, при цьому деталь з номером i виготовяється за pi секунд. Специфіка підприємтсва "Авто-2012" полягає у тому, що там одночасно может виготовлятись лише одна деталь двигуна. Для виробництва деяких деталей необхідно мати попередньо виготовлений набір інших деталей.

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

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

Вхідні дані

Перший рядок містить n (1 ≤ n ≤ 105) натуральних чисел p1, p2, ..., pn, які визначають час виготовлення кожної деталі у секундах.

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

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

Вихідні дані

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