Багата Родина#2759
Під час вивчення історії королівських родин ви хочете визначити багатство кожної родини. Хоча у вас є різні дані про 'статки' кожної особи в різні історичні періоди, спадкування ускладнює завдання через можливість подвійного підрахунку. Один зі способів оцінити багатство родини — підсумувати статки набору з людей так, щоб жоден із них не був предком іншого з цього набору. Багатством родини вважається максимальна сума, яку можна отримати серед усіх таких наборів з людей. Оскільки історичні записи подають статки лише чоловіків, родинне дерево — це просте дерево, у якому кожен чоловік має рівно одного батька та будь-яку (можливо, нульову) кількість синів. Можна вважати, що в родині була одна особа, яка є пращуром усіх інших.
Вхід складається з кількох наборів даних. Кожен набір починається рядком із двох цілих чисел: (1 \leq N \leq 150000) — кількість людей у родині, та (1 \leq k \leq 300) — розмір набору. Далі йде рядків із двома невід'ємними цілими числами: номер батька та статки людини (1 \leq i \leq N). Кожна особа позначається числом від до включно. Є рівно одна людина без батька — це вказується номером батька . Статки вказано в мільйонах; кожен член родини має статки від мільйона до мільярда.
Для кожного набору даних виведіть максимальну суму (у мільйонах), яку можна отримати для набору з людей, що задовольняє зазначені умови. Якщо неможливо вибрати набір з людей без порушення обмежень, виведіть impossible.
Приклад 1