Background

Translated from ROIR 2022 D2T3.

A country has $n$ cities, numbered from $1$ to $n$, and the capital is city $1$.

The computer network of this country is built as follows: each city has a connection hub, and hubs can be connected to some other hubs via wired communication links. Between any two cities, there is exactly one communication path; in other words, the network forms a tree. For city $i(i > 1)$, denote by $p_i$ the first city on the path from city $i$ to the capital.

The network is planned to be upgraded by replacing some existing wired links with more advanced optical communication links. Optical links can only be laid where an existing wired link is. The cost to replace the communication link connecting city $i$ and $p_i$ is $w_i$. Due to technical limitations, any connection hub can be directly connected to at most $k$ other hubs.

Problem Description

The Ministry of Communications wants to make an upgrade plan to improve the connectivity of optical communication links. Therefore, it needs to upgrade as many communication links as possible. If multiple plans upgrade the same number of links, it wants the total upgrade cost to be as small as possible; that is, among those plans, choose the one with the minimum total cost.

Help the experts of the Ministry of Communications choose which communication links to upgrade.

Input Format

The first line contains two integers $n$ and $k$.

The next $n-1$ lines describe the communication links. The $(i-1)$-th of these lines contains two integers: $p_i$ and $w_i$ ($1 \le p_i < i, 0 \le w_i \le 10^9$).

Output Format

Output two integers $cnt$ and $cost$, representing the maximum number of communication links that can be upgraded and the minimum cost to upgrade those links.

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

Hint

In Sample $1$, the network configuration before and after the upgrade is shown in the figure below. The links to be upgraded are shown in bold. The maximum number of links that can be upgraded is $4$.

In Sample $2$, the network configuration before and after the upgrade is shown in the figure below. The links to be upgraded are shown in bold. The upgrade cost is shown next to each edge (communication link). In the optimal solution, the total cost of the upgraded links is $27$, and the maximum number of links that can be upgraded is $6$.

In the original problem, there are $13$ subtasks, but Luogu does not support setting more than $10$ subtasks. The original problem has $321$ testdata points, but Luogu does not support setting more than $100$ testdata points. Therefore, this problem only keeps the last $100$ testdata points, and does not use bundled tests.

All data satisfy $2 \le n \le 10^5, 1 \le k \le 100$.

Translated by ChatGPT 5