시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 51 17 16 41.026%

문제

n(1≤n≤10,000)개의 정점을 갖는 부모가 있는 트리(Rooted Tree)를 생각해 보자. 각각의 간선에는 음 아닌 정수로 가중치가 있다. 이 트리의 높이는 루트에서 가장 멀리 떨어져 있는 정점까지의 거리를 의미한다.

이 트리의 간선의 가중치를 1씩 줄일 때마다 1만큼의 비용이 든다. 쉽게 생각하면, 가중치가 x인 간선의 가중치를 y(x≥y≥0)로 줄일 때, x-y만큼의 비용이 든다는 의미이다. 문제를 쉽게 하기 위해서 음 아닌 정수에서 음 아닌 정수로 줄이는 경우만 생각하기로 하자.

우리는 몇 개의 간선의 가중치를 적절히 줄여서, 이 트리의 높이를 H(H≥0, H는 정수)로 만드려고 한다. 이 때, 최소의 비용을 들여서 높이를 H로 만드는 것이 목적이다.

입력

첫째 줄에 정점의 개수 n과 H가 주어진다. 다음 n개의 줄에는 1번 정점부터 n번 정점까지 차례로, 각 정점의 부모 정점과, 그 정점에서 부모 정점까지의 거리(간선의 가중치)가 주어진다. 루트의 경우에는 부모 정점과 비용 대신에 0 두 개가 주어진다. 각 가선의 가중치의 총 합은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 최소 비용을 출력한다.

예제 입력

5 1
0 0
1 1
2 1
2 1
1 2

예제 출력

2

힌트