favorite We need a little bit of your help to keep things running, click on this banner to learn more



Scientists discovered a biochip, which can divide itself into several new biochips. Herewith the parent-biochip disappears. Each biochip has its own size of memory, the size does not depend on the parent memory size. Then the biochip might be either used (stopping its division), or it will continue division in a similar manner.

Scientists prepared tree-like schemes of biochip-division process and they know the exact structure of the tree consisting of n elements, including the memory size of each of possible biochips descendants. Make a program to choose from the tree exactly m biochips total memory size of which is the biggest possible. Pay attention to the fact that when we are choosing a biochip, we can't choose neither any of its ancestors nor descendants.


The first line contains two integers n and m - number of elements of the tree and number of biochips to be chosen (1n200 000, 1m500).

The following n lines contain two non-negative integers each: number of the parent in the tree and the size of the chip's memory x (1x1000). Each biochip has a unique number ranging from 1 to n inclusively. The line with i number includes information about a biochip with number i - 1. Just one biochip doesn't have a parent and it's parent is written as 0.

It's guaranteed that it's possible to choose m biochips.


Print one integer - maximal possible amount of memory of m chosen biochips.

Time limit 1 second
Memory limit 64 MiB
Input example #1
7 3
2 100
0 1000
2 150
3 100
3 5
5 100
2 50
Output example #1
Source 2012 VIII Zhautykov Olympiad Almaty, Kazakhstan, January 17