Wealthy Family#2759
While studying the history of royal families, you want to determine the wealth of each family. Although you have various net worth figures for each individual throughout history, inheritance causes complications due to double counting. One way to estimate a family's wealth is to sum the net worth of a set of people so that no one in the set is an ancestor of another in the set. The family's wealth is the maximum sum achievable over all such sets of people. Since historical records provide the net worths only for male family members, the family tree is a simple tree, where each male has exactly one father and a non-negative number of sons. You may assume there is one person who is an ancestor of all other family members.
The input consists of several cases. Each case begins with a line containing two space-separated integers: (1 \leq N \leq 150000), the number of people in the family, and (1 \leq k \leq 300), the size of the set. The next lines each contain two non-negative integers: the parent number and the net worth of person (1 \leq i \leq N). Each person is identified by a number between and , inclusive. There is exactly one person with no parent, which is indicated with a parent number of . Net worths are given in millions; each family member has a net worth of at least million and at most 1\,000\,000\,000.
For each case, print the maximum sum (in millions) achievable over all sets of people that satisfy the above constraints. If it is impossible to select a set of people without violating the constraints, print impossible instead.
Example 1