Çox Yollu Hekayə
Siz bir proqramçısınız və tanışlıq simulyasiya oyunlarının bir alt janrı olan gözəl qız oyunlarını sevirsiniz. "Floatable Heart" adlı oyun keçən cümə günü buraxılıb və artıq evinizə çatıb. Bu oyunda bir neçə hekayə mövcuddur. Bütün hekayələri tamamladığınızda, əsas qəhrəman Megumi'nin xüsusi bir fiqurunu əldə edə bilərsiniz. Buna görə də oyunu oynamağa tələsirsiniz! Amma gəlin bir az sakitləşək və əvvəlcə bütün hekayələri ən qısa zamanda necə tamamlayacağımızı düşünək.
Əslində, oyunların budaqlanma nöqtələrinin strukturunu bilmək üçün xüsusi bir bacarığınız var. Bu bacarıqdan istifadə edərək, bu oyunda n budaqlanma nöqtəsi olduğunu və i-ci budaqlanma nöqtəsinin k_i seçimləri olduğunu öyrəndiniz. Bu oyun o qədər mürəkkəbdir ki, çoxlu marşrutlar i-ci budaqlanma nöqtəsinə çata bilər. Siz həmçinin fərqinə vardınız ki, i-ci budaqlanma nöqtəsindən başqa bir budaqlanma nöqtəsinə (və ya sona) keçmək c_{ij } dəqiqə çəkir, əgər i-ci budaqlanma nöqtəsinin j-ci seçimini seçsəniz. Əlbəttə ki, bütün seçimləri bütün budaqlanma nöqtələrində seçməli və bir budaqlanma nöqtəsi ilə başqa bir budaqlanma nöqtəsi (və ya son) arasındakı hekayələri oxumalısınız ki, bütün bu hekayələri tamamlayasınız. Bundan əlavə, oyunun əvvəlindən birinci budaqlanma nöqtəsinə qədər oynamaq üçün yalnız əhəmiyyətsiz vaxt tələb olunduğunu fərz edə bilərsiniz ("reset").
Oyunun təlimatında deyilir ki, bu oyunda "Tez Saxla" adlı əlavə bir xüsusiyyət var və bu xüsusiyyət, hazırda oynadığınız nöqtəni qeyd etməyə və daha sonra istənilən vaxt ora qayıtmağa imkan verir. Lakin, bu xüsusiyyət bir səhv səbəbindən işləmir. Beləliklə, sona çatdığınızda və ya oyunu yarıda dayandırdığınızda hər dəfə birinci budaqlanma nöqtəsindən başlamalısınız. Bu səhvi düzəltmək üçün heç bir yamaq hələ dərc olunmayıb. Bu, ən sürətli oyunçular üçün tətbiq olunan bir çətinlikdir.
Yaxşı, gəlin bütün hekayələri ən qısa zamanda tamamlamanın nə qədər vaxt alacağını təxmin edək.
Giriş verilənləri
Məlumat dəsti aşağıdakı formatda verilir.
n
k_1 t_11 c_12 ... t_1k1 c_1k1
...
k_n t_n1 c_n2 ... t_nkn c_nkn
Məlumat dəstinin ilk sətri bu oyundakı budaqlanma nöqtələrinin sayını göstərən bir tam ədəd n (2 ≤ n ≤ 1000) ehtiva edir. Aşağıdakı n sətr budaqlanma nöqtələrini təsvir edir. i-ci sətir ID nömrəsi i olan budaqlanma nöqtəsini təsvir edir. İlk tam ədəd k_i (0 ≤ k_i ≤ 50) i-ci budaqlanma nöqtəsindəki seçimlərin sayıdır. k_i ≥ 0 i-ci budaqlanma nöqtəsinin son olduğunu göstərir. Növbəti 2k_i tam ədədlər t_ij (1 ≤ t_ij ≤ n) və c_ij (0 ≤ c_ij ≤ 300) seçimlərin məlumatıdır. t_ij j-ci seçimi seçdiyiniz zaman növbəti budaqlanma nöqtələrinin ID nömrələrini göstərir. c_ij i-ci budaqlanma nöqtəsi ilə t_ij-ci budaqlanma nöqtəsi arasındakı hekayəni oxumaq üçün lazım olan vaxtı göstərir. ID nömrəsi 1 olan budaqlanma nöqtəsi birinci budaqlanma nöqtəsidir. Bütün budaqlanma nöqtələrinin və sonların birinci budaqlanma nöqtəsindən əlçatan olduğunu fərz edə bilərsiniz. Həmçinin, oyunda heç bir döngə olmadığını, yəni bir budaqlanma nöqtəsinə bir dəfədən çox reset etmədən çatılmayacağını fərz edə bilərsiniz.
Çıxış verilənləri
Ən qısa vaxtı bir sətirdə çap edin.