Анюта та Google
Десятикласниця Аня захоплюється мікробіологією і готує доповідь про нові види вірусів. Як відомо, Google - кращий друг людей, тому Аняа з ним дружить. При підготовці до доповіді вона багато працювала у пошуковій системі і зібрала гарну інформацію. Працювала Аня наступним чином:
Спочатку вона ввела пошуковий запит в Google і отримала декілька посилань, які їй здаються достатньо цікавими.
Аня знає, що якщо завантажити якусь сторінок зі списку вже знайдених і занесених у її список, там можуть виявитись посилання на інші сторінки. Ці сторінки також можна завантажити. Саме так вона і діяла, завантажуючи усі сторінки, які її цікавили.
Аня повторювала завантаження, доки у її списку не виявилось рівно n різних сторінок.
Але практично у той момент, коли доповідь була готова, Мурзик - любимий кіт Ані - у черговий раз перегриз провід - і Інтернет пропав! А це означає, що остання потрібна сторінка не була закачана. На жаль, усі сторінки Аня заносила у список під номерами 1, 2, ..., n, а повні адреси сторінок в Інтернеті Аня не записувала. І тепер у Ані виникла необхідність знайти і скачати цю останню сторінку.
Завинившого Мурзика закрили на кухні, на що той дуже образився. Провід замінили. І тепер Аня хоче пройти ще раз від пошукового запиту у Google до останньої сторінки у її списку використаних джерел, тобто завантажити саме ту сторінку, прочитати яку завадив Мурзик. Зараз у Ані є список сторінок, причому для кожної сторінки відомі наступні дані:
об'єм сторінки в байтах,
список сторінок, на які можна перейти з заданої сторінки.
Ані дуже цікаво - який мінімальний об'єм байтів вона повинна скачати, щоб пройти по посиланням до потрібної сторінки? Допоможіть їй розв'язати цю задачу!
Вхідні дані
Перший рядок містить кількість Інтернет-сторінок n у списку. Далі йде n рядків, i-ий рядок містить ціле число p[i] - об'єм сторінки в байтах, та m[i] - кількість сторінок, на які можна перейти з i-ої. Далі у цьому ж рядку міститься m[i] цілих чисел - номери сторінок, на які можна перейти з i-ої. Перша сторінка у цьому списку - Google. Остання сторінка у списку - це та, шлях до якої Аня хоче знайти. Сторінки нумеруються з 1. Значення n не перевищує 100. Об'єм кожної сторінки не дорівнює нулю і не перевищує 1 мегабайт, задається в байтах.
Вихідні дані
Вивести одне число - мінімальну кількість байт, які потрібно скачати, щоб пройти по посиланням від першої сторінки до останньої. Гарантується, що такий шлях завжди існує.
