Кожен раз, коли у світі відбувається значна подія, наша реальність розгалужується на декілька - у залежності від того, як завершилась ця подія. Після цього існує вже не лише наша основна реальність, але й відокремлені від неї у моменти появи різних завершень. Одного разу один архімаг вирішив зробити світ кращим. Таке грандіозне завдання не під силу одному архімагу, тому він вирішив знайти самого себе ще у \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} - мінімальну можливу енергію, яка потрібна архімагу для подорожі.