트리 높이 줄이기

정점 N개(1 ≤ N ≤ 10,000)로 이루어진 루트 트리가 있다. 각 간선에는 음이 아닌 정수 가중치가 있다. 트리의 높이는 루트에서 가장 멀리 떨어진 정점까지의 거리이다.

비용 1을 들이면 어떤 간선의 가중치를 1 줄일 수 있다. 즉, 가중치가 x인 간선을 y(0 ≤ y ≤ x)로 줄이는 비용은 x - y이다. 가중치는 항상 음이 아닌 정수로만 줄인다.

몇 개의 간선 가중치를 줄여 트리의 높이가 H(0 ≤ H ≤ 150,000, H는 정수) 이하가 되도록 만들려고 한다. 필요한 최소 비용을 구하라.

첫째 줄에 정점의 개수 N과 목표 높이 H가 주어진다.

이어서 N개의 줄에 1번 정점부터 N번 정점까지 차례로 각 정점의 부모 정점 번호와 그 정점에서 부모 정점까지의 거리(간선의 가중치)가 주어진다. 루트 정점의 줄에는 부모 정점과 거리 대신 0 0이 주어진다.

모든 가중치는 음이 아닌 정수이며, 모든 간선 가중치의 합은 1,000,000,000을 넘지 않는다.

트리의 높이가 H 이하가 되도록 간선 가중치를 줄이는 데 드는 최소 비용을 첫째 줄에 출력한다.