Ailə Sərvəti#3342
Tarix boyu varlı ailələrin tarixini araşdıran tədqiqatçılar, hər bir ailənin nə qədər sərvət topladığını öyrənmək istəyirlər. Tarix boyunca hər bir fərd üçün müxtəlif 'xalis dəyər' rəqəmləri mövcuddur, lakin miras səbəbindən ikiqat sayma ilə bu rəqəmləri toplamaq çətindir. Ailənin sərvətini təxmin etməyin bir yolu, elə bir K nəfərlik dəstənin xalis dəyərini toplamaqdır ki, bu dəstədəki heç kim digər birinin nə əcdadı, nə də nəslindən olsun. Ailənin sərvəti, belə K nəfərlik dəstələrdən əldə edilə biləcək maksimum cəmdir. Tarixi qeydlərdə yalnız kişi ailə üzvlərinin xalis dəyəri olduğu üçün, ailə ağacı sadə bir ağacdır və hər bir kişinin dəqiq bir atası və qeyri-mənfi sayda oğlu var. Həmçinin, bütün digər ailə üzvlərinin əcdadı olan yalnız bir nəfər var.
Bir ailə ağacı haqqında məlumat verildikdə, bu ölçü ilə ailənin sərvəti nə qədərdir?
Girişdə bir neçə test halı olacaq. Hər bir test halı iki tam ədədlə başlayacaq:
N K
Burada N (1 ≤ N ≤ 100,000) qeydlərdə olan ailə üzvlərinin ümumi sayıdır və K (1 ≤ K ≤ 1,000) istənilən dəstənin ölçüsüdür.
Növbəti N sətirdən hər biri iki tam ədəd saxlayacaq:
P W
Burada P (0 ≤ P ≤ N) həmin ailə üzvünün valideynini göstərir. Ailə üzvləri 1-dən N-ə qədər nömrələnir, və i-ci ailə üzvünün valideyni və sərvəti i-ci sətirdə verilir. Yalnız bir kök olacaq, P=0 ilə. Ağacın dərinliyi 1,000-dən böyük olmayacaq və əlbəttə ki, heç bir dövrə malik olmayacaq. W (1 ≤ W ≤ 1,000) həmin ailə üzvünün sərvətidir (milyonlarla).
Giriş iki 0 olan bir sətirlə bitəcək.
Hər bir test halı üçün, dəstədəki heç bir üzvün digər bir üzvün nə əcdadı, nə də nəslindən olmadığı K ailə üzvünün sərvətlərinin maksimum cəmini (milyonlarla) öz sətirində çıxarın. Əgər belə K düyün tapa bilmirsinizsə, onda 0 çıxarın. Artıq boşluqlar çıxarmayın və cavabları boş sətirlərlə ayırmayın.
Nümunə 1