Vasiyə kömək et
Vasya, Ümumberlyand yaz bahar proqramlaşdırma toplantıları üçün növbəti müsabiqəni hazırlayır. O, əyləncəli tədbirləri sevdiyi və hava da buna uyğun olduğu üçün hazırlıq üçün çox az vaxtı qalıb. Vasya bu vaxtı ən səmərəli şəkildə istifadə etmək istəyir. Qarşısında duran məsələlərdən biri, bir qovluqdan digərinə mümkün qədər tez keçməkdir. O, sevimli fayl meneceri "Near Commandir"ə o qədər öyrəşib ki, başqa proqramdan istifadə edə bilmir, çünki bu, ona daha çox vaxt aparardı. Bu menecer bir neçə sadə əməliyyat edə bilir: fayl və alt qovluqlar siyahısında bir mövqe yuxarı hərəkət etmək, aşağı hərəkət etmək, hazırda siyahıda seçilmiş alt qovluğa daxil olmaq və əgər bu, ana qovluqsa, kataloq ağacında bir səviyyə yuxarı qalxmaq. Bu sadə əməliyyatların hər biri Vasya üçün 1 saniyə çəkir. Vasya həmçinin fayl və alt qovluqların cari qovluqdakı sırasını dəyişdirmək əməliyyatını tətbiq edərək sürətləndirə bilər, bu əməliyyat Vasya üçün t saniyə çəkir. Qovluqdakı fayllar ada, ölçüyə və son dəyişiklik vaxtına görə sıralana bilər. Son iki halda, eyni ölçü və vaxta malik fayllar ada görə sıralanır. Bir qovluq daxilində fayl və qovluq adları unikaldır. İndi o, fayl sisteminin ağacında harada olduğunu bilsə, lazım olan fayla keçmək üçün nə qədər vaxt lazım olduğunu bilmək istəyir. Əvvəlcə cari qovluqdakı fayllar ada görə sıralanır, yeni qovluğa daxil olduqda fayllar da Vasya tərəfindən əlavə vaxt sərf edilmədən ada görə sıralanır.
Giriş verilənləri
Fayl sistemi kökü vurğulanmış ağacla verilir. Birinci sətirdə n və t (1 ≤ n ≤ 100000, 0 ≤ t ≤ 10) - ağacın ölçüsü və fayl sırasının dəyişmə vaxtı verilir. Sonrakı n sətirdə 4 ədəd p_i name_i fsize_i date_i (1 ≤ i ≤ n. p_i - əcdadın zirvəsinin nömrəsi, əgər bu -1dirsə, bu yeganə zirvə kökdür, name_i - faylın adı, boş olmayan, ən çox 10 latın hərfindən ibarət sətir, fsize_i - faylın ölçüsü, 0 ≤ fsize_i ≤ 10000. date_i - faylın son dəyişiklik vaxtı, 0 ≤ date_i ≤ 10000) verilir. Son sətirdə iki ədəd 0 ≤ s, f < n - hazırda dayandığımız zirvənin nömrəsi və çatmalı olduğumuz zirvənin nömrəsi verilir. Zirvələr girişdə təqdim olunan sıraya görə nömrələnir.
Çıxış verilənləri
Bir tam ədəd çıxarın - minimal saniyə sayı.