Семейное состояние
Исследователи, изучающие историю состоятельных семей, стремятся определить накопленное состояние каждой семьи. Для каждого человека в истории существуют различные показатели "чистого капитала", но их суммирование затруднено из-за двойного учета, возникающего при наследовании. Один из способов оценить богатство семьи — это сложить чистый капитал группы из K человек так, чтобы никто в этой группе не был предком или потомком другого члена группы. Богатство семьи определяется как максимальная сумма, достижимая для всех таких групп из K человек. Поскольку исторические записи содержат только чистый капитал мужских членов семьи, генеалогическое дерево представляет собой простое дерево, в котором у каждого мужчины есть ровно один отец и ненулевое количество сыновей. Также существует ровно один человек, который является предком всех остальных членов семьи.
Дана информация о генеалогическом дереве. Каково богатство семьи по этой мере?
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с двух целых чисел:
N K
Где N (1 ≤ N ≤ 100,000) — общее количество членов семьи в записях, а K (1 ≤ K ≤ 1,000) — размер желаемой группы людей.
Каждая из следующих N строк содержит два целых числа:
P W
Где P (0 ≤ P ≤ N) указывает на родителя этого члена семьи. Члены семьи пронумерованы от 1 до N, при этом родитель и состояние члена семьи i появляются в i-й строке. Будет один корень с P=0. Глубина дерева не будет больше 1,000, и, конечно, оно не будет содержать циклов. W (1 ≤ W ≤ 1,000) — это богатство (в миллионах) этого члена семьи.
Входные данные заканчиваются строкой с двумя 0.
Выходные данные
Для каждого теста выведите одно целое число в отдельной строке, которое является максимальной суммой (в миллионах) состояний группы из K членов семьи в дереве, где ни один член группы не является предком или потомком другого члена группы. Если вы не можете найти K таких узлов, выведите 0. Не выводите лишние пробелы и не разделяйте ответы пустыми строками.