19381번 - Ascending Tree 다국어

문제

You are given a rooted tree. Each vertex of the tree is labeled with an integer. If you pay one dollar, you can change (increment or decrement) the label of a vertex by one.

You want to change the labels such that, for each vertex, its label is strictly greater than any of the labels assigned to its children. Compute the minimum cost required to satisfy this condition.

입력

The first line contains two integers: $N,ドル the number of vertices in the tree, and $C_1,ドル the label assigned to the root. The vertices are numbered 1ドル$ through $N,ドル and the root is vertex 1ドル$ (1ドル \le N \le 10^5$).

The next $N - 1$ line describe non-root vertices. The $i$-th line contains two integers: $P_i,ドル the number of the parent of the vertex $i,ドル and $C_i,ドル the label assigned to the vertex $i$ (1ドル \le P_i < i,ドル $-10^9 \le c_i \le 10^9$).

출력

Print the minimum cost on a single line.

제한

힌트

The figure on the left is the input configuration for the first sample. The figure on the right is a possible final configuration: the label of each parent is strictly greater than that of its child.