Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.
Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в \(K\) реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё \(N - 1\) реальностей. Для удобства они были занумерованы числами от \(1\) до \(N\), при этом его собственная реальность имеет номер \(1\), а посетить ему необходимо реальности с номерами \(2, 3, \ldots, K + 1\).
Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени \(0\)). Исследование показало, что реальность с номером \(i\) ответвилась от реальности с номером \(P_i\) в момент времени \(T_i\). Из каждой реальности с номером \(i\) архимаг может переместиться
-
в любую ответвившуюся от неё, то есть в любую \(j\), такую что \(P_j = i\);
-
в \(P_i\), если \(i\) — не Начальная реальность.
Другими словами, возможны лишь переходы вида \(i \leftrightarrows P_i\). На каждый такой переход в любую сторону архимаг затрачивает \(T_i-T_{P_i} > 0\) условных единиц энергии.
Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером \(1\), посетить все реальности с номерами от \(2\) до \(K + 1\) (в любом порядке) и затем вновь вернуться в \(1\). Любую реальность при этом разрешается посещать сколько угодно раз.
Формат входных данных
Сначала вводятся два целых числа \(N\) и \(K\) (\(0 \leqslant K < N \leqslant 100\,000\)): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт \(N\) пар целых чисел, \(i\)-я пара — это \(P_i\) и \(T_i\) (\(1 \leqslant P_i \leqslant N\), \(0 \leqslant T_i \leqslant 10^6\); для Начальной реальности \(P_i=T_i=0\)).
Гарантируется, что ответвившаяся реальность появилась строго позже породившей (\(T_i > T_{P_i})\), и что маг может при желании добраться до любой из \(N\) реальностей.
Формат выходных данных
Выведите единственное число \(E\) — минимальную возможную энергию, которая потребуется архимагу для путешествия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
4 2
4 6
1 9
0 0
1 7
|
30
|