ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1210. Добрые духи

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Иванушка-дурачок живет на планете нулевого уровня. Жить на такой планете — дело неблагодарное. Ужасный климат, 80-часовая рабочая неделя, некрасивые девушки… Как и любой другой житель его планеты, он мечтает попасть на планету N-го уровня. В рай.
На каждой планете i-того уровня есть несколько гиперпространственных переходов на некоторые из планет (i+1)-го уровня (а вот обратного хода нет). Каждый переход, однако, охраняется духом. Как правило, эти духи — злые, они требуют за каждый переход много галактических кредиток. Ведь все хотят попасть на планету более высокого уровня. А удовольствие стоит денег. Больше, чем Иванушка может себе представить. Впрочем, бывают и экстраординарные ситуации, скажем, нехватка рабочей силы на одной из планет более высокого уровня, и тогда духи — стражи переходов — становятся добрыми. Они, случается, даже сами дают кредитки, лишь бы кто-нибудь пошел на их планету.
Чтобы воплотить в жизнь свою мечту о жизни на райской планете, Иванушка сделал две вещи. Во-первых, он раздобыл полную карту Вселенной. На этой карте написано, сколько сегодня берут или дают духи за переход с той или иной планеты на ту или иную планету следующего уровня. Во-вторых, он нанял команду молодых талантливых программистов, чтобы те помогли ему проложить по этой карте такой маршрут с его планеты на какую-нибудь планету уровня N, чтобы он потратил на этом маршруте как можно меньше кредиток. А лучше бы — чтобы заработал как можно больше!

Исходные данные

В первой строке указано число N (0 < N < 30) — количество уровней планет на карте Иванушки. Далее следует N блоков информации, описывающих переходы между уровнями. А именно, i-й блок описывает схему переходов с планет (i−1)-го уровня на планеты i-го уровня. Блоки разделяются строками, содержащими один символ "*". Планеты на каждом уровне нумеруются последовательными целыми положительными числами от единицы. На каждом уровне не более 30 планет. На нулевом уровне только одна планета — та, на которой живет Иванушка. В первой строке блока записано число Ki — количество планет на i-м уровне. Далее следуют Ki строк — по одной для каждой планеты i-го уровня. В каждой такой строке перечислены через пробел номера планет предыдущего, (i-1)-го уровня, с которых можно перейти на данную планету, и стоимости таких переходов. Стоимость каждого перехода — целое число от −32768 до 32767; отрицательная стоимость некоторого перехода обозначает тот факт, что добрый дух готов доплатить за такой переход. Каждая строка с описанием переходов на планету завершается нулем.

Результат

Выведите единственное целое число — минимальную для Иванушки стоимость перехода на какую-нибудь планету N-го уровня. Ответ может быть и отрицательным — это будет означать, что Иванушка не только доберется до райской планеты, но и заработает при этом некоторое количество кредиток. Известно, что хотя бы один путь с Иванушкиной планеты на одну из планет N-го уровня существует.
Problem illustration

Пример

исходные данныерезультат
3
2
1 15 0
1 5 0
*
3
1 -5 2 10 0
1 3 0
2 40 0
*
2
1 1 2 5 3 -5 0
2 -19 3 -20 0
-1
Автор задачи: Леонид Волков
Источник задачи: USU Open Collegiate Programming Contest October'2002 Junior Session