Reducing Tree Height

You are given a rooted tree with N vertices (1 ≤ N ≤ 10,000). Each edge has a nonnegative integer weight. The height of the tree is the distance from the root to the farthest vertex.

Reducing the weight of an edge by 1 costs 1. Equivalently, reducing an edge of weight x to y (0 ≤ y ≤ x) costs x - y. Edge weights are only reduced from nonnegative integers to nonnegative integers.

Reduce the weights of some edges so that the height of the tree becomes at most H (0 ≤ H ≤ 150,000, H is an integer). Find the minimum possible cost.

The first line contains the number of vertices N and the target height H.

The next N lines describe vertices 1 through N in order. Each line contains the parent vertex number of that vertex and the distance from the vertex to its parent, which is the edge weight. For the root vertex, the line contains 0 0 instead.

All weights are nonnegative integers, and the sum of all edge weights is at most 1,000,000,000.

Print the minimum cost required to reduce edge weights so that the tree height is at most H.