1761. Путешествия в реальности

Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько – в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неЄь в моменты появления разных исходов. Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в `K` реальностях и выполнить эту задачу вместе. ПроведЄьнное теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё `N-1` реальностей. Для удобства они были занумерованы числами от 1 до `N`, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами `2,\ 3,\ …,\ K\ +\ 1`.

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером `i` ответвилась от реальности с номером `P_i` в момент времени `T_i`. Из каждой реальности с номером `i` архимаг может переместиться

Другими словами, возможны лишь переходы вида `i\ ↔\ P_i`. На каждый такой переход в любую сторону архимаг затрачивает `T_i\ -\ T_{P_i}\ >\ 0` условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до `K\ +\ 1` (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.

Сначала вводятся два целых числа `N` и `K` (`0\ ≤\ K\ <\ N\ ≤\ 100\ 000`): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт `N` пар целых чисел, `i`-я пара – это `P_i` и `T_i` (`1\ ≤\ P_i\ ≤\ N`, `0\ ≤\ T_i\ ≤\ 10^6`; для Начальной реальности `P_i\ =\ T_i\ =\ 0`). Гарантируется, что ответвившаяся реальность появилась строго позже породившей (`T_i\ >\ T_{P_i}`), и что маг может при желании добраться до любой из `N` реальностей.

Выведите единственное число `E` – минимальную возможную энергию, которая потребуется архимагу для путешествия.

5 2
4 2
4 6
1 9
0 0
1 7

30