I. Путь и k вершин
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан ориентированный граф, являющийся корневым деревом. Дуги графа направлены от сыновей к отцам, и из каждой вершины можно по дугам прийти в корень. В вершинах графа написаны целые числа. Гарантируется, что все числа различные.

Рассмотрим все пути из листьев в корень; здесь листом считается вершина, у которой нет сыновей. Для каждого пути посчитаем сумму $$$k$$$ максимальных чисел, встречающихся в его вершинах — или всех этих чисел, если в пути меньше $$$k$$$ вершин. Найдите максимальную такую сумму.

Входные данные

В первой строке записаны через пробел два целых числа $$$n$$$ и $$$k$$$ — количество вершин в графе и ограничение на количество взятых вершин на пути ($$$1 \leq n \leq 300\,000$$$, $$$1 \leq k \leq 300\,000$$$). В следующих $$$n$$$ строках задан граф. В $$$i$$$-й из этих строк записаны через пробел два целых числа $$$p_i$$$ и $$$q_i$$$; здесь $$$p_i$$$ — номер вершины-предка $$$i$$$-й вершины, а $$$q_i$$$ — число, записанное в этой вершине ($$$0 \leq q_i \leq 10^9$$$). Для корня дерева $$$p_i = 0$$$; для всех остальных вершин $$$1 \leq p_i \leq n$$$. Числа $$$q_i$$$ все различны.

Гарантируется, что заданный граф является корневым деревом.

Выходные данные

В первой строке выведите одно число — максимальную сумму не более чем $$$k$$$ чисел на некотором пути из листа в корень.

Примеры
Входные данные
5 2
0 1
1 2
1 3
2 4
3 5
Выходные данные
8
Входные данные
7 3
0 15
1 1
2 21
3 99
1 14
5 20
6 100
Выходные данные
135