Задача 3. Оптические каналы связи ≡

Условие

Всего во Флатландии n городов, пронумерованных от 1 до n, столица Флатландии имеет номер 1. Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города i, где i > 1, обозначим первый город на маршруте от города i до столицы как p_i.

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город i с городом p_i, равна w_i. Из-за ограничений технологии любой центр подключения может быть непосредственно подключен оптическими каналами не более чем к k другим центрам.

Министерство связи Флатландии хочет составить такой план модернизации каналов, чтобы после его выполнения связность сети по оптическим каналам связи была как можно выше. Поэтому необходимо выбрать для модернизации как можно больше каналов. Но при этом стоимость модернизации желательно минимизировать, поэтому при равном количестве необходимо выбрать для модернизации каналы с минимальной суммарной стоимостью.

Помогите специалистам министерства выбрать каналы для модернизации.

Формат входных данных

На первой строке ввода находятся два целых числа n и k (2 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100).

На следующих n − 1 строках заданы описания каналов, (i − 1)-я из этих строк содержит два целых числа: p_i и w_i (1 ≤ p_i ≤ i, 0 ≤ w_i ≤ 10⁹).

Формат выходных данных

Выведите два целых числа cnt и cost: максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Ограничения

2 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100

1 ≤ p_i ≤ i, 0 ≤ w_i ≤ 10⁹

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 4. Стоимость модернизации любого канала равна 0 и не показана.

Есть и другие подходящие решения, в которых модернизируется 4 канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 6. Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна 27.

Примеры тестов

8 2
1 0
1 0
1 0
2 0
2 0
2 0
1 0

4 0

8 3
1 5
1 2
1 4
2 6
2 7
2 2
1 6

6 27