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