Ann, a schoolchild of the 10th grade, is fond of microbiology and now she is preparing a report on new types of viruses. As you know, Google is the best friend of people, so Ann make friends with him. During the preparation for the report, she worked a lot with the search engine and collected good information. Ann worked as follows:

• First, she made a search query in Google and received several links that she found interesting enough.
• Ann knows that if she load a page from the already found list, there may be links to other pages. These pages can also be downloaded. That is how she acted, loading all the pages of interest to her.
• Ann repeated downloads until her list contained exactly n different pages.

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

Провинившегося Мурзика заперли в кухне, на что тот очень обиделся. Провод заменили. И теперь Анечка хочет пройти еще раз от поискового запроса в Google до последней страницы в ее списке использованных источников, то есть загрузить именно ту страницу, прочитать которую помешал Мурзик. Сейчас у Ани есть список страниц, причем для каждой страницы известны следующие данные:

• объем страницы в байтах,
• список страниц, на которые можно перейти от данной страницы.

Анечке очень интересно - какой минимальный объем байтов она должна скачать, чтобы пройти по ссылкам до нужной страницы? Помогите ей решить эту задачу!

Input

Первая строка содержит количество Интернет-страниц n в списке. Далее следуют n строк, i-ая строка содержит целое число pi - объем страницы в байтах и mi - количество страниц, на которые можно перейти с i-ой. Далее в этой же строке содержатся mi целых чисел - номера страниц, на которые можно перейти с i-ой. Первая страница в этом списке - Google. Последняя страница в списке - это та, путь к которой Аня хочет найти. Страницы нумеруются с 1. Значение n не превышает 100. Объем каждой страницы не равен нулю и не превышает 1 мегабайта, задается в байтах.

Output

Вывести одно число - минимальное количество байт, которые нужно скачать, чтобы пройти по ссылкам от первой страницы до последней. Гарантируется, что такой путь всегда существует.