You are given a directed graph that is a rooted tree. The edges of the graph are directed from children to parents, and from each vertex, it is possible to reach the root through the edges. Each vertex of the graph contains an integer. It is guaranteed that all these integers are distinct.
Consider all paths from the leaves to the root; here, a leaf is a vertex without children. For each path, calculate the sum of the $$$k$$$ largest numbers occurring in its vertices, or all of them if there are fewer than $$$k$$$ numbers on the path. Find the maximum such sum.
The first line contains two integers $$$n$$$ and $$$k$$$ separated by a space — the number of vertices in the graph and the limit on the number of vertices taken on the path ($$$1 \leq n \leq 300\,000$$$, $$$1 \leq k \leq 300\,000$$$).
The next $$$n$$$ lines define the graph. The $$$i$$$-th of these lines contains two integers $$$p_i$$$ and $$$q_i$$$ separated by a space; here, $$$p_i$$$ is the number of the parent vertex of the $$$i$$$-th vertex, and $$$q_i$$$ is the number written in this vertex ($$$0 \leq q_i \leq 10^9$$$). For the root of the tree, $$$p_i = 0$$$; for all other vertices, $$$1 \leq p_i \leq n$$$. The numbers $$$q_i$$$ are all distinct.
It is guaranteed that the given graph is a rooted tree.
On the first line, output a single integer: the maximum sum of at most $$$k$$$ numbers on some path from a leaf to the root.
5 20 11 21 32 43 5
8
7 30 151 12 213 991 145 206 100
135
