부유한 가문

어느 왕가의 역사를 연구하면서, 각 가문이 얼마나 부유했는지 알고 싶습니다. 역사 기록에는 여러 인물의 '순자산' 값이 남아 있지만, 상속으로 인한 이중 계산 때문에 이 값들을 단순히 더하면 정확하지 않습니다.

한 가문의 부를 추정하는 한 가지 방법은, 서로 조상-후손 관계가 없는 $k$명을 골라 그들의 순자산을 모두 더하는 것입니다. 즉, 고른 $k$명 중 누구도 다른 사람의 조상이 되어서는 안 됩니다. 가문의 부는 이러한 모든 $k$명 집합에 대해 얻을 수 있는 합의 최댓값으로 정의합니다.

역사 기록에는 남성 가족 구성원의 순자산만 남아 있으므로, 가계도는 각 남성이 정확히 한 명의 아버지와 0명 이상의 아들을 가지는 하나의 트리입니다. 다른 모든 구성원의 조상이 되는 사람이 정확히 한 명 존재한다고 가정할 수 있습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스의 첫 줄에는 공백으로 구분된 두 정수 $N$과 $k$가 주어집니다. $N$($1 \le N \le 150{,}000$)은 가족 구성원의 수이고, $k$($1 \le k \le 300$)는 골라야 하는 집합의 크기입니다.

이어지는 $N$개의 줄 중 $i$번째 줄에는 공백으로 구분된 두 음이 아닌 정수, 즉 $i$번 사람의 부모 번호와 순자산이 주어집니다($1 \le i \le N$). 각 사람은 $1$부터 $N$까지의 번호로 식별됩니다. 기록상 부모가 없는 사람은 정확히 한 명이며, 그 사람의 부모 번호는 $0$으로 표시됩니다. 순자산은 100만 단위로 주어지고, 각 구성원의 실제 순자산은 100만 이상 10억 이하이므로 주어지는 각 값은 $1$ 이상 $1000$ 이하입니다.

입력은 파일의 끝까지 계속됩니다.

각 케이스마다, 위 조건을 만족하는 모든 $k$명 집합에 대해 얻을 수 있는 합의 최댓값(100만 단위)을 한 줄에 출력합니다. 조건을 어기지 않고 $k$명을 고르는 것이 불가능하다면, 대신 'impossible'을 출력합니다.