eolymp
bolt
Try our new interface for solving problems
Problems

Biochips

Biochips

Time limit 1 second
Memory limit 64 MiB

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.

Input data

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 thesize 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.

Output data

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

Examples

Input example #1
7 3
2 100
0 1000
2 150
3 100
3 5
5 100
2 50
Output example #1
300
Source 2012 VIII Zhautykov Olympiad Almaty, Kazakhstan, January 17