Щоразу, коли в світі відбувається значуща подія, наша реальність розгалужується на кілька в залежності від результату цієї події. Після цього існує вже не тільки наша основна реальність, а й розгалужені від неї в моменти появи різних результатів.

Якось один архімаг вирішив зробити світ кращим. Таке грандіозна задача не під силу одному архімагу, тому він вирішив знайти самого себе ще в \(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 ≤ 100 000\)): кількість доступних реальностей і кількість реальностей, які необхідно відвідати.

Далі йде \(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\) реальностей.

Формат вихідних даних

Виведіть число Е - мінімальну можливу енергію, яка знадобиться архімагу для подорожі.

Приклад вхідних даних

5 2
4 2
4 6
1 9
0 0
1 7

Приклад вихідних даних

30