Історія з багатьма шляхами
Ви програміст, який захоплюється іграми про симпатичних дівчат, зокрема симуляторами побачень. Нещодавно вийшла гра "Плавуче Серце", і ви щойно отримали її. У цій грі є кілька історій, і після завершення всіх ви отримаєте спеціальну фігурку головної героїні, Мегумі. Тому ви хочете якомога швидше почати грати. Але спочатку варто подумати, як завершити всі історії в найкоротший час.
Ви маєте особливу здатність, яка дозволяє бачити структуру точок розгалуження в іграх. Завдяки цій здатності ви дізналися, що в грі є 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-й рядок описує точку розгалуження з ID номером 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 вказує ID наступної точки розгалуження, коли ви обираєте j-й вибір. c_ij вказує час на прочитання історії між i-ю точкою і t_ij-ю точкою. Точка розгалуження з ID 1 є першою. Ви можете припустити, що всі точки розгалуження та кінці досяжні з першої точки. Також можна припустити, що в грі немає циклів, тобто жодна точка не може бути досягнута більше одного разу без скидання.
Вихідні дані
Виведіть найкоротший час в одному рядку.