Family Fortune

While studying the history of wealthy families, researchers want to know how large a fortune each family has actually amassed. History records several "net worth" figures for each individual, but simply adding them up is inaccurate because of the double counting caused by inheritance. One way to estimate a family's wealth is to choose a set of $K$ people, none of whom is an ancestor or a descendant of any other in the set, and add up their net worth. The family's wealth is then defined as the maximum such sum over all valid sets of $K$ people.

Because the records contain only the net worth of the male family members, the family tree is a simple tree in which every male has exactly one father and any number (possibly zero) of sons. There is also exactly one person who is an ancestor of every other member.

Given the family tree, what is the family's wealth under this definition?

The input contains several test cases. Each test case begins with two integers:

N K

where $N$ $(1 \le N \le 100{,}000)$ is the total number of recorded family members and $K$ $(1 \le K \le 1{,}000)$ is the size of the desired set.

Each of the next $N$ lines contains two integers:

P W

where $P$ $(0 \le P \le N)$ is the parent of that member. Members are numbered from $1$ to $N$, and the $i$-th of these lines describes the parent and fortune of member $i$. There is a single root, whose member has $P = 0$. The tree is at most $1{,}000$ deep and, of course, contains no cycles. $W$ $(1 \le W \le 1{,}000)$ is that member's wealth (in millions).

The input ends with a line containing two zeros.

For each test case, print on its own line a single integer: the maximum sum (in millions) of the fortunes of a set of $K$ family members in which no member is an ancestor or descendant of any other. If no such set of $K$ members exists, print $0$. Do not print extra spaces, and do not separate answers with blank lines.