Богатая семья
Изучая историю королевских семей, вы хотите выяснить, насколько богата каждая семья. У вас есть данные о 'чистом капитале' каждого человека на протяжении истории, но задача усложняется из-за двойного учета, вызванного наследованием. Один из способов оценить богатство семьи — это сложить чистый капитал набора из k людей так, чтобы никто в наборе не был предком другого. Богатство семьи — это максимальная сумма, достижимая для всех таких наборов из k людей. Поскольку исторические записи содержат только чистый капитал мужских членов семьи, генеалогическое древо представляет собой простое дерево, в котором у каждого мужчины есть ровно один отец и ненулевое количество сыновей. Вы можете предположить, что есть один человек, который является предком всех остальных членов семьи.
Входные данные
Входные данные состоят из нескольких случаев. Каждый случай начинается со строки, содержащей два целых числа, разделенных пробелом: N (1 ≤ N ≤ 150000), количество людей в семье, и k (1 ≤ k ≤ 300), размер набора. Следующие N строк содержат два неотрицательных целых числа, разделенных пробелом: номер родителя и чистый капитал человека i (1 ≤ i ≤ N). Каждый человек идентифицируется номером от 1 до N, включительно. Есть ровно один человек, у которого нет родителя в исторических записях, и это будет указано номером родителя 0. Чистый капитал указан в миллионах, и каждый член семьи имеет чистый капитал не менее 1 миллиона и не более 1 миллиарда.
Выходные данные
Для каждого случая выведите максимальную сумму (в миллионах), достижимую для всех наборов из k людей, удовлетворяющих указанным выше ограничениям. Если невозможно выбрать набор из k людей, не нарушая ограничения, выведите 'невозможно'.