바이오칩 Batch 컴파일 명령

저명한 과학자인 석환이는 스스로 분할할 수 있는 바이오칩을 발견해 냈습니다. 분할하면서 부모 바이오칩은 사라지게 됩니다. 각 바이오칩에는 저장 가능한 메모리가 있으며, 그 크기는 부모의 메모리에 따라 결정되지는 않습니다. 석환이는 분할을 멈추고 바이오칩을 사용하거나, 비슷한 방식으로 계속 분할할 수 있습니다.

석환이는 바이오칩이 분할되는 과정을 트리 형태로 나타내었습니다. 이 트리는 $N$개의 노드가 있으며, 각 노드에는 자신의 메모리 크기가 있습니다. 부모 노드는 자신의 자식 노드들로 분할될 수 있습니다.

정확히 $M$개의 바이오칩을 선택해서 메모리 크기의 합이 최대화되도록 하는 프로그램을 작성하세요. 바이오칩 하나를 선택하면, 그 바이오칩의 조상 노드와 자손 노드 모두 선택할 수 없다는 것을 명심하세요.

입력 형식

첫 번째 줄에 트리의 노드 수 $N$과 선택해야 할 바이오칩의 수 $M$이 주어집니다. ($1 \le N \le 200 000, 1 \le M \le 500$)

다음 $N$개 줄에는 각각 두 개의 정수가 주어집니다: 첫 번째는 부모 노드의 번호이고, 두 번째는 해당 바이오칩의 메모리 크기 $x$ ($1 \le x \le 1000$)입니다. 각 바이오칩에는 $1$부터 $N$까지의 자연수 번호가 붙어 있습니다. $i$번째 줄에는 $i-1$번 바이오칩의 정보가 들어 있습니다. 단 하나의 바이오칩은 부모 노드가 없으며, 이 노드의 부모는 0으로 주어집니다.

$M$개의 바이오칩을 선택할 수 있다는 것은 보장됩니다.

출력 형식

첫 번째 줄에 $M$개의 바이오칩을 잘 선택해서 얻을 수 있는 가장 큰 메모리를 출력합니다.

예제

참고

20%의 데이터에 대해 $N \le 20, M \le 10.$

60%의 데이터에 대해 $N \le 10000, M \le 100.$