Путешествия в реальности
Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько - в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.
Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N-1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K+1.
Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером P_i в момент времени T_i. Из каждой реальности с номером i архимаг может переместиться
в любую ответвившуюся от неё, то есть в любую j, такую что P_j = i;
в P_i, если i - не Начальная реальность.
Другими словами, возможны лишь переходы вида i → P_i. На каждый такой переход в любую сторону архимаг затрачивает T_{i }- T{P_i} > 0 условных единиц энергии.
Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K+1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.
Входные данные
Сначала вводятся два целых числа N и K (0 ≤ K < N ≤ 100000): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт 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 - минимальную возможную энергию, которая потребуется архимагу для путешествия.