Varlı Ailə#2759
Kral ailələrinin tarixini öyrənərkən, hər bir ailənin sərvətini müəyyənləşdirmək istəyirsiniz. Hər bir fərdin tarix boyu müxtəlif 'xalis dəyər' göstəriciləri olsa da, miras paylanması ikiqat saymalar səbəbindən çətinləşir. Ailənin sərvətini təxmin etməyin bir yolu budur: nəfərdən ibarət elə bir dəstin xalis dəyərlərini toplamaq lazımdır ki, dəstdə heç kim digər bir nəfərin əcdadı olmasın. Ailənin sərvəti belə bütün mümkün nəfərlik dəstlər üzrə əldə edilə bilən maksimum cəmdir. Tarixi qeydlər yalnız kişi ailə üzvlərinə dair sərvətləri göstərdiyi üçün ailə ağacının quruluşu sadədir: hər kişinin yalnız bir atası və sıfır və ya daha çox oğlu var. Tək bir nəfərin bütün ailə üzvlərinin əcdadı olduğu qəbul edilir.
Girişdə bir neçə tapşırıq verilir. Hər tapşırıq bir sətrdə iki boşluqla ayrılmış tam ədəd ilə başlayır: (1 \leq N \leq 150000) — ailə üzvlərinin sayı və (1 \leq k \leq 300) — dəstin ölçüsü. Sonra ardıcıl sətir gəlir. Hər sətirdə iki qeyri-mənfi tam ədəd verilir: -ci şəxsin ata nömrəsi və onun xalis dəyəri (1 \leq i \leq N). Hər bir şəxsin nömrəsi -dən -ə kimidir. Tam olaraq bir nəfərin atası yoxdur, bu da ata nömrəsi olmaqla işarə edilir. Sərvət milyonlarla ifadə olunur; hər bir ailə üzvünün sərvəti ən azı milyon, ən çoxu isə milyarddır.
Hər tapşırıq üçün yuxarıda göstərilən şərtləri pozmadan nəfərlik dəstdə əldə edilməsi mümkün olan maksimum cəmi (milyonla) çap edin. Əgər belə dəst seçmək mümkün deyilsə, **impossible** çap edin.
Nümunə 1