Travels in Reality
Whenever a significant event occurs in the world, our reality splits into multiple branches, each representing a different outcome of that event. As a result, not only does our original reality persist, but new realities also emerge from these branching points.
An archmage once aspired to improve the world. However, such a monumental task was beyond the capabilities of just one archmage, so he decided to collaborate with versions of himself from K other realities. His research revealed that, in addition to his own reality, there are N-1 other realities. For simplicity, these realities are numbered from 1 to N, with his own reality being number 1. He needs to visit the realities numbered 2, 3, ..., K+1.
Each reality, except for one Initial reality, branched off from another. The Initial reality has always existed (its number can be any, and it is considered to have appeared at time 0). The research indicated that the reality numbered i branched off from the reality numbered P_i at time T_i. From any reality numbered i, the archmage can move:
to any reality that branched off from it, i.e., to any j such that P_j = i;
to P_i, if i is not the Initial reality.
In essence, only transitions of the type i → P_i are possible. For each such transition, regardless of direction, the archmage expends T_{i} - T{P_i} > 0 units of energy.
The task is to determine the minimum amount of energy required for the archmage to start in reality number 1, visit all realities numbered from 2 to K+1 (in any order), and then return to reality 1. Any reality can be visited multiple times if necessary.
Input
The input begins with two integers N and K (0 ≤ K < N ≤ 100000), representing the total number of realities and the number of realities that need to be visited, respectively. This is followed by N pairs of integers, where the i-th pair consists of P_i and T_i (1 ≤ P_i ≤ N, 0 ≤ T_i ≤ 10^6; for the Initial reality, P_i=T_i=0).
It is guaranteed that a branched reality appeared strictly later than the one it originated from (T_i > T{P_i}), and that the archmage can reach any of the N realities if needed.
Output
Output a single number E - the minimum possible energy required for the archmage's journey.