Многопутевая история
Вы программист, увлеченный играми с красивыми девушками, особенно симуляторами свиданий. Недавно вышла игра "Плавающее Сердце", и вы только что получили её. В этой игре несколько сюжетных линий. Завершив все, вы получите специальную фигурку главной героини, Мегуми. Поэтому вы хотите как можно быстрее начать играть! Но давайте сначала подумаем, как пройти все истории в кратчайшие сроки.
У вас есть особое умение, позволяющее видеть структуру развилок в играх. Благодаря этому вы узнали, что в игре есть n развилок, и у i-й развилки k_i вариантов выбора. Игра настолько сложна, что к i-й развилке могут вести несколько путей. Вы также заметили, что требуется c_{ij } минут, чтобы перейти от i-й развилки к другой развилке (или к завершению), если выбрать j-й вариант i-й развилки. Вам нужно выбрать все варианты на всех развилках и прочитать истории между развилками, чтобы завершить все сюжетные линии. Можно предположить, что на возврат к началу игры ("сброс") и прохождение от начала до первой развилки уходит незначительное время.
В руководстве к игре указано, что в ней есть функция "Быстрое сохранение", позволяющая записать текущую точку игры и вернуться к ней позже. Однако из-за ошибки эта функция не работает. Поэтому вам приходится начинать с первой развилки каждый раз, когда вы завершаете игру или выходите из неё. Патч для исправления этой ошибки ещё не выпущен. Это испытание для самых быстрых игроков.
Давайте оценим, сколько времени потребуется для завершения всех историй в кратчайшие сроки.
Входные данные
Набор данных задан в следующем формате.
n
k_1 t_11 c_12 ... t_1k1 c_1k1
...
k_n t_n1 c_n2 ... t_nkn c_nkn
Первая строка набора данных содержит одно целое число n (2 ≤ n ≤ 1000), обозначающее количество развилок в игре. Следующие n строк описывают развилки. i-я строка описывает развилку с идентификатором i. Первое целое число k_i (0 ≤ k_i ≤ 50) — это количество выборов на i-й развилке. k_i = 0 означает, что i-я развилка является завершением. Следующие 2k_i целых чисел t_ij (1 ≤ t_ij ≤ n) и c_ij (0 ≤ c_ij ≤ 300) — это информация о выборах. t_ij обозначает идентификаторы следующих развилок при выборе j-го варианта. c_ij обозначает время на прочтение истории между i-й развилкой и t_ij-й развилкой. Развилка с идентификатором 1 является первой развилкой. Можно предположить, что все развилки и завершения достижимы из первой развилки. Также можно предположить, что в игре нет циклов, то есть ни одна развилка не может быть достигнута более одного раза без сброса.
Выходные данные
Выведите кратчайшее время в одной строке.