Sehrbazlıq#6982
Sehr tökülməsi davamlı bir prosesdir. Başlanğıcda müəyyən miqdarda enerji (mana ilə ölçülən) ilə başlayırıq və bu enerjini sehr elementlərini çağırmaq üçün istifadə edirik. Hər bir elementi istənilən miqdarda enerji sərf edərək dərhal çağırmaq mümkündür və bu anda həmin element sehrin bir hissəsinə çevrilir, güc (saniyədə mana ilə ölçülən) təmin edir. Bu güc zamanla enerjinin yığılmasına səbəb olur ki, bu da əlavə elementlərin çağırılması üçün istifadə edilə bilər. Prosesi, sehrimizin ümumi güc çıxışı tələb olunan səviyyəyə çatana qədər davam etdiririk.
Bu prosesdə bir çətinlik var: təcrübəli sehrbazlar sehrləri daha təsirli şəkildə tökmək üçün istifadə edirlər. Hər bir elementin çağırılmasını dəstəkləyən bir valideyn elementi ola bilər və əgər valideyn elementi artıq mövcuddursa, onu adətən olduğundan yarı enerji ilə çağırmaq mümkündür. Məsələn, əgər element A elementi B və elementi C dəstəkləyirsə, biz əvvəlcə tam qiymətə 1 vahid element A çağırıb, sonra yarı qiymətə 0.5 vahid element B və 0.5 vahid element C çağırıb bilərik. Əgər sonra 0.5 daha çox vahid element C çağırsaq, bu hissə yenidən tam enerji qiymətinə olacaq, çünki 1 vahid element A artıq digər elementləri dəstəkləyir. Qeyd edək ki, bütün 3 element sehrə tam güc çıxışını təmin edir; dəstək vermək heç bir şəkildə güc çıxışına mane olmur, nə də bir elementi sərf etmir.
Başlanğıc enerji miqdarı, hədəf güc miqdarı və çağırılmaq üçün mövcud olan sehr elementlərinin təsviri verildikdə, hədəf güc miqdarına minimum vaxtda çatacaq bir sehr tökməyi öyrənin.
Giriş bir neçə test halından ibarət olacaq. Hər bir test halı N, E və P tam ədədləri ilə başlayan bir sətirdən ibarətdir, burada elementlərin sayı, başlanğıc enerji (mana ilə) və hədəf güc (saniyədə mana ilə) müvafiq olaraq göstərilir. Bu sətirdən sonra N sətir gəlir, i-ci sətir elementi i üç tam ədədlə təsvir edir: çağırılma enerji xərci, güc çıxışı və valideyn elementin indeksi (1-indeksli; əgər element i valideyn elementi yoxdursa parent_i = 0).
Məhdudiyyətlər bunlardır:
1 ≤ N ≤ 1000, 1 ≤ E ≤ 10^9, 1 ≤ P ≤ 10^9.
1 ≤ e_i ≤ 10^9 bütün i üçün, 0 ≤ p_i ≤ 10^9 bütün i üçün, 0 ≤ parent_i ≤ N bütün i üçün.
Ən azı bir pi müsbət olacaq.
Heç bir element öz əcdadı deyil; başqa sözlə, heç bir element özünü, birbaşa və ya dolayı yolla dəstəkləyə bilmir.
Giriş N = E = P = 0 olan bir hal ilə bitəcək, bu işlənməməlidir.
Hər bir test halı üçün hədəf gücə çatmaq üçün tələb olunan minimum saniyə sayını (yuxarı yuvarlaqlaşdırılmış) göstərən tək bir sətir çap edin.
Nümunə 1