Reallıqda Səyahətlər
Hər dəfə dünyada əhəmiyyətli bir hadisə baş verəndə, reallığımız bu hadisənin nəticəsinə görə bir neçə yerə ayrılır. Bu andan etibarən, yalnız bizim əsas reallığımız deyil, həm də müxtəlif sonluqların meydana gəldiyi anlarda ondan ayrılmış reallıqlar mövcuddur.
Bir gün bir arximag dünyanı daha yaxşı etmək qərarına gəldi. Belə böyük bir vəzifə bir arximagın gücündə deyil, ona görə də o, özünü başqa K reallıqda tapıb bu vəzifəni birlikdə yerinə yetirməyə qərar verdi. Aparılan nəzəri tədqiqat göstərdi ki, onun olduğu reallıqdan başqa, daha N-1 reallıq mövcuddur. Rahatlıq üçün bu reallıqlar 1-dən N-ə qədər nömrələnmişdir, onun öz reallığı 1 nömrəsinə malikdir və o, 2, 3, ..., K+1 nömrəli reallıqları ziyarət etməlidir.
Deyildiyi kimi, hər bir reallıq bir vaxtlar başqa bir reallıqdan ayrılmışdır, bir Başlanğıc reallıq istisna olmaqla, o həmişə mövcud olmuşdur (onun nömrəsi istənilən ola bilər; onun 0 zaman anında meydana gəldiyi qəbul edilir). Tədqiqatlar göstərdi ki, i nömrəli reallıq T_i zaman anında P_i nömrəli reallıqdan ayrılmışdır. Hər bir i nömrəli reallıqdan arximag aşağıdakı yerlərə keçə bilər:
ondan ayrılmış istənilən reallığa, yəni P_j = i olan istənilən j nömrəli reallığa;
P_i reallığına, əgər i Başlanğıc reallıq deyilsə.
Başqa sözlə, yalnız i → P_i keçidləri mümkündür. Arximag hər iki istiqamətdə belə bir keçid üçün T_{i }- T{P_i} > 0 şərti enerji vahidi sərf edir.
Arximagın 1 nömrəli reallıqdan başlayaraq 2-dən K+1-ə qədər nömrəli bütün reallıqları (istənilən ardıcıllıqla) ziyarət edib yenidən 1-ə qayıtması üçün lazım olan minimal enerji miqdarını tapmaq lazımdır. İstənilən reallığı istənilən qədər ziyarət etmək icazəlidir.
Giriş verilənləri
Əvvəlcə iki tam ədəd N və K (0 ≤ K < N ≤ 100000) daxil edilir: mövcud reallıqların sayı və ziyarət edilməli reallıqların sayı. Sonra N cüt tam ədəd gəlir, i-ci cütlük P_i və T_i (1 ≤ P_i ≤ N, 0 ≤ T_i ≤ 10^6; Başlanğıc reallıq üçün P_i=T_i=0) təşkil edir.
Zəmanət verilir ki, ayrılmış reallıq onu yaradan reallıqdan daha gec meydana gəlmişdir (T_i > T{P_i}), və arximag istədiyi təqdirdə N reallıqdan istənilən birinə çata bilər.
Çıxış verilənləri
Tək bir ədəd E çıxarın - arximagın səyahəti üçün lazım olan minimal mümkün enerji.