Дан ориентированный граф, являющийся корневым деревом. Дуги графа направлены от сыновей к отцам, и из каждой вершины можно по дугам прийти в корень. В вершинах графа написаны целые числа. Гарантируется, что все числа различные.
Рассмотрим все пути из листьев в корень; здесь листом считается вершина, у которой нет сыновей. Для каждого пути посчитаем сумму $$$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 20 11 21 32 43 5
8
7 30 151 12 213 991 145 206 100
135
