I. Path And k Vertices
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

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.

Input

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.

Output

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.

Examples
Input
5 2
0 1
1 2
1 3
2 4
3 5
Output
8
Input
7 3
0 15
1 1
2 21
3 99
1 14
5 20
6 100
Output
135