Иванушка-дурачок живет на планете нулевого уровня. Жить на такой планете — дело неблагодарное. Ужасный климат, 80-часовая рабочая неделя, некрасивые девушки… Как и любой другой житель его планеты, он мечтает попасть на планету N-го уровня. В рай.

На каждой планете i-того уровня есть несколько гиперпространственных переходов на некоторые из планет (i+1)-го уровня (а вот обратного хода нет). Каждый переход, однако, охраняется духом. Как правило, эти духи — злые, они требуют за каждый переход много галактических кредиток. Ведь все хотят попасть на планету более высокого уровня. А удовольствие стоит денег. Больше, чем Иванушка может себе представить. Впрочем, бывают и экстраординарные ситуации, скажем, нехватка рабочей силы на одной из планет более высокого уровня, и тогда духи — стражи переходов — становятся добрыми. Они, случается, даже сами дают кредитки, лишь бы кто-нибудь пошел на их планету.

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

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

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