Wealthy Family

While studying the history of a royal family, you want to know how wealthy the family was. The historical records contain many 'net worth' figures for individuals, but simply adding them up is misleading because inheritance causes double counting.

One way to estimate a family's wealth is to choose $k$ people, none of whom is an ancestor of another, and add up their net worths. The wealth of the family is the maximum such sum over every valid set of $k$ people.

Because the records preserve the net worth of male family members only, the family tree is a single tree in which every male has exactly one father and zero or more sons. You may assume there is exactly one person who is an ancestor of every other family member.

The input consists of several test cases. The first line of each case contains two space-separated integers $N$ and $k$: $N$ ($1 \le N \le 150{,}000$) is the number of people in the family, and $k$ ($1 \le k \le 300$) is the size of the set to choose.

Each of the next $N$ lines contains two space-separated non-negative integers: the parent number and the net worth of person $i$ ($1 \le i \le N$), given on the $i$-th of these lines. Each person is identified by a number from $1$ to $N$. Exactly one person has no parent in the records, and that person's parent number is given as $0$. Net worths are given in millions, and each member's net worth is between $1$ million and $1$ billion inclusive, so each given value is between $1$ and $1000$.

The input continues until end of file.

For each case, print on its own line the maximum sum (in millions) achievable over all sets of $k$ people satisfying the constraints above. If it is impossible to choose $k$ people without violating the constraints, print 'impossible' instead.