Bessinin ad günü#11172
Bessinin ad günü münasibətilə Fermer Con ona öz ən yaxşı tarlalarından birində sərbəst otlamağa icazə verdi.
Tarla nömrələnmiş ot sahəsindən ibarətdir, hər birinin özünəməxsus ot keyfiyyət dəyəri var. Əgər Bessi keyfiyyəti olan otu yeyərsə, o vahid enerji alır. Hər sahə ən çoxu qonşu sahə ilə ikitərəfli yollarla birləşir və qonşu sahələr arasında keçid etmək üçün Bessi vahid enerji sərf edir.
Bessi başlanğıc mövqe kimi istənilən sahəni seçə bilər. O, mümkün qədər çox enerji toplayana qədər otlamaq istəyir.
Təəssüf ki, Bessi seçici bir inəkdir: müəyyən keyfiyyətdə ot yedikdən sonra o, artıq eyni və ya daha aşağı keyfiyyətli otu heç vaxt yeməyəcək. Ancaq Bessi ot yeməyərək sahələrdən keçməyə tamamilə etiraz etmir. Üstəlik, ona sonradan dadlı bir şey üçün geri qayıtmaq üçün yüksək keyfiyyətli otu olan sahədən onu yemədən keçmək faydalı ola bilər.
Bessinin toplaya biləcəyi maksimum enerji miqdarını təyin etməyə kömək edin.
Birinci sətirdə iki tam ədəd və e~(1 \le n \le 1000, 1 \le e \le 10^6) verilir.
Sonrakı sətirdən hər biri bir ot sahəsini təsvir edir. Hər sətir iki tam ədəd və ehtiva edir, burada q~(1 \le q \le 10^6) — həmin sahədəki otun keyfiyyəti, isə qonşu sahələrin sayıdır.
Bu sətirdəki növbəti tam ədəd qonşu sahələrin nömrələrini göstərir.
Bessinin toplaya biləcəyi maksimum enerji miqdarını çap edin.
Bessi nömrəli sahədən başlayır və orada bitən otu yeyərək vahid enerji alır. Sonra o, yolla nömrəli sahəyə gedir və yolda vahid enerji itirir. O, nömrəli sahədəki daha aşağı keyfiyyətli otu yeməkdən imtina edir və geriyə, nömrəli sahəyə qayıdır, bu zaman daha vahid enerji itirir. Nəhayət, o, nömrəli sahədəki otu yeyir və vahid enerji alır. Nəticədə o, vahid enerji əldə edir.
Nümunə 1