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

Анюта та Google

Анюта та Google

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
prb3870-01

Десятикласниця Аня захоплюється мікробіологією і готує доповідь про нові види вірусів. Як відомо, Google - кращий друг людей, тому Аняа з ним дружить. При підготовці до доповіді вона багато працювала у пошуковій системі і зібрала гарну інформацію. Працювала Аня наступним чином:

  • Спочатку вона ввела пошуковий запит в Google і отримала декілька посилань, які їй здаються достатньо цікавими.

  • Аня знає, що якщо завантажити якусь сторінок зі списку вже знайдених і занесених у її список, там можуть виявитись посилання на інші сторінки. Ці сторінки також можна завантажити. Саме так вона і діяла, завантажуючи усі сторінки, які її цікавили.

  • Аня повторювала завантаження, доки у її списку не виявилось рівно n різних сторінок.

Але практично у той момент, коли доповідь була готова, Мурзик - любимий кіт Ані - у черговий раз перегриз провід - і Інтернет пропав! А це означає, що остання потрібна сторінка не була закачана. На жаль, усі сторінки Аня заносила у список під номерами 1, 2, ..., n, а повні адреси сторінок в Інтернеті Аня не записувала. І тепер у Ані виникла необхідність знайти і скачати цю останню сторінку.

Завинившого Мурзика закрили на кухні, на що той дуже образився. Провід замінили. І тепер Аня хоче пройти ще раз від пошукового запиту у Google до останньої сторінки у її списку використаних джерел, тобто завантажити саме ту сторінку, прочитати яку завадив Мурзик. Зараз у Ані є список сторінок, причому для кожної сторінки відомі наступні дані:

  • об'єм сторінки в байтах,

  • список сторінок, на які можна перейти з заданої сторінки.

Ані дуже цікаво - який мінімальний об'єм байтів вона повинна скачати, щоб пройти по посиланням до потрібної сторінки? Допоможіть їй розв'язати цю задачу!

Вхідні дані

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

Вихідні дані

Вивести одне число - мінімальну кількість байт, які потрібно скачати, щоб пройти по посиланням від першої сторінки до останньої. Гарантується, що такий шлях завжди існує.

prb3870-02

Приклад

Вхідні дані #1
6
100 3 6 2 3
100 2 5 3
100 1 4
100 2 5 2
100 0
20 1 1
Вихідні дані #1
120
Джерело 2011 Задачі відбіркового туру Всеросійської командної олімпіади школярів