Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько - в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов. Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в \textbf{K} реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё \textbf{N}-\textbf{1} реальностей. Для удобства они были занумерованы числами от \textbf{1} до \textbf{N}, при этом его собственная реальность имеет номер \textbf{1}, а посетить ему необходимо реальности с номерами \textbf{2}, \textbf{3}, ..., \textbf{K+1}. Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени \textbf{0}). Исследование показало, что реальность с номером \textbf{i} ответвилась от реальности с номером \textbf{P_i} в момент времени \textbf{T_i}. Из каждой реальности с номером \textbf{i} архимаг может переместиться \begin{itemize} \item в любую ответвившуюся от неё, то есть в любую \textbf{j}, такую что \textbf{P_j} = \textbf{i}; \item в \textbf{P_i}, если \textbf{i} - не Начальная реальность. \end{itemize} Другими словами, возможны лишь переходы вида \textbf{i} → \textbf{P_i}. На каждый такой переход в любую сторону архимаг затрачивает \textbf{T_\{i \}}- \textbf{T}\{\textbf{P_i}\} > \textbf{0} условных единиц энергии. Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером \textbf{1}, посетить все реальности с номерами от \textbf{2} до \textbf{K}+\textbf{1} (в любом порядке) и затем вновь вернуться в \textbf{1}. Любую реальность при этом разрешается посещать сколько угодно раз. \InputFile Сначала вводятся два целых числа \textbf{N} и \textbf{K} (\textbf{0} ≤ \textbf{K} < N ≤ \textbf{100000}): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт \textbf{N} пар целых чисел, \textbf{i}-я пара - это \textbf{P_i} и \textbf{T_i} (\textbf{1} ≤ \textbf{P_i} ≤ \textbf{N}, \textbf{0} ≤ \textbf{T_i} ≤ \textbf{10^6}; для Начальной реальности \textbf{P_i}=\textbf{T_i}=\textbf{0}). Гарантируется, что ответвившаяся реальность появилась строго позже породившей (\textbf{T_i} > \textbf{T}\{\textbf{P_i}\}), и что маг может при желании добраться до любой из \textbf{N} реальностей. \OutputFile Выведите единственное число \textbf{E} - минимальную возможную энергию, которая потребуется архимагу для путешествия.