Сімейний статок
Під час вивчення історії заможних родин дослідники прагнуть визначити, наскільки велике багатство кожна родина накопичила. Існують різні значення "чистої вартості" для кожної особи в історії, але підсумовування ускладнюється через подвійний підрахунок, викликаний спадкуванням. Один зі способів оцінити багатство родини — це підсумувати чисту вартість набору з K людей так, щоб ніхто в наборі не був предком або нащадком когось іншого в наборі. Багатство родини — це максимальна сума, досягнута для всіх таких наборів з K людей. Оскільки історичні записи містять лише чисту вартість чоловіків-членів родини, родинне дерево є простим деревом, у якому кожен чоловік має рівно одного батька і ненегативну кількість синів. Також є рівно одна особа, яка є предком усіх інших членів родини.
Дано інформацію про родинне дерево, яке є багатством родини за цим мірилом?
Вхідні дані
Вхід міститиме кілька тестових випадків. Кожен тестовий випадок починатиметься з двох цілих чисел:
N K
Де N (1 ≤ N ≤ 100,000) — загальна кількість членів родини в записах, а K (1 ≤ K ≤ 1,000) — розмір бажаного набору людей.
Кожен з наступних N рядків міститиме два цілих числа:
P W
Де P (0 ≤ P ≤ N) вказує на батька цього члена родини. Члени родини пронумеровані від 1 до N, з батьком і багатством члена родини i, що з'являються на i-му рядку. Буде один корінь, з P=0. Дерево не матиме глибини більше ніж 1,000, і, звичайно, не матиме жодних циклів. W (1 ≤ W ≤ 1,000) — це багатство (в мільйонах) цього члена родини.
Вхід закінчиться рядком з двома 0.
Вихідні дані
Для кожного тестового випадку виведіть одне ціле число в окремому рядку, яке є максимальною сумою (в мільйонах) статків набору з K членів родини в дереві, де жоден член набору не є предком або нащадком будь-якого іншого члена набору. Якщо ви не можете знайти K таких вузлів, тоді виведіть 0. Не виводьте зайвих пробілів і не розділяйте відповіді порожніми рядками.