가문의 재산

부유한 가문의 역사를 연구하는 학자들은 각 가문이 실제로 얼마만큼의 부를 축적했는지 알고 싶어 한다. 역사 속 각 인물에게는 여러 '순자산' 기록이 남아 있지만, 상속으로 인한 중복 계산 때문에 이를 단순히 모두 더하는 것은 정확하지 않다. 한 가문의 부를 추정하는 한 가지 방법은, 집합에 속한 누구도 다른 사람의 조상이나 후손이 아닌 $K$명의 집합을 골라 그들의 순자산을 합하는 것이다. 이때 가문의 부는 그러한 모든 $K$명 집합에 대해 얻을 수 있는 합의 최댓값으로 정의한다.

역사 기록에는 남성 구성원의 순자산만 남아 있으므로, 가계도는 모든 남성이 정확히 한 명의 아버지를 가지고 0명 이상의 아들을 두는 단순한 트리 구조를 이룬다. 또한 다른 모든 구성원의 조상이 되는 사람이 정확히 한 명 존재한다.

가계도 정보가 주어질 때, 위 정의에 따른 가문의 부는 얼마인가?

입력에는 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수로 시작한다.

N K

여기서 $N$ $(1 \le N \le 100{,}000)$은 기록에 남은 가문 구성원의 총수이고, $K$ $(1 \le K \le 1{,}000)$은 고르려는 집합의 크기이다.

이어지는 $N$개의 줄에는 각각 두 정수가 주어진다.

P W

여기서 $P$ $(0 \le P \le N)$는 해당 구성원의 부모를 나타낸다. 구성원은 $1$부터 $N$까지 번호가 매겨지며, $i$번째 줄에는 구성원 $i$의 부모와 재산이 적혀 있다. 루트는 하나뿐이며, 그 구성원은 $P=0$을 가진다. 트리의 깊이는 $1{,}000$을 넘지 않고, 당연히 사이클도 존재하지 않는다. $W$ $(1 \le W \le 1{,}000)$는 해당 구성원의 재산(단위: 백만)이다.

입력은 두 개의 $0$으로 이루어진 줄로 끝난다.

각 테스트 케이스마다, 트리에서 서로가 서로의 조상이나 후손이 아닌 $K$명으로 이루어진 집합이 가질 수 있는 재산의 합의 최댓값(단위: 백만)을 한 줄에 하나의 정수로 출력한다. 그러한 $K$명을 고를 수 없다면 $0$을 출력한다. 불필요한 공백을 넣지 말고, 답 사이에 빈 줄도 넣지 않는다.