Problem Background

Translated from ROIR 2022 D2T3.

A country has $n$ cities, numbered from $1$ to $n$, with the capital numbered as $1$.

The country's computer network is structured such that each city has a connection center, which can be linked to other centers via wired communication channels. There exists a unique communication path between any two cities, in other words, the network forms a tree. For city $i (i > 1)$, we denote the first city on the path from city $i$ to the capital as $p_i$.

A plan is in place to upgrade the network by replacing some existing wired channels with more advanced optical communication channels. Optical channels can only be laid in the locations of the existing wired channels. The cost to replace the communication channel connecting city $i$ and $p_i$ is $w_i$. Due to technical limitations, any connection center can directly connect to at most $k$ other centers.

Problem Description

The communications department aims to enhance the connectivity of the optical communication channels by selecting as many channels as possible for upgrade. However, they also wish to minimize the upgrade cost when the number of channels is the same. Therefore, among the same number of channels, they choose those with the smallest total cost.

Help the communications department experts select the channels to be upgraded.

Input Format

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

The next $n-1$ lines describe the communication channels, with the $(i-1)$-th line containing 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 channels that can be upgraded and the minimum cost to upgrade these channels.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4 0

Sample Input #2

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

Sample Output #2

6 27

Notes

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

In Sample 2, the network configuration before and after the upgrade is shown in the figure below. The channels to be upgraded are indicated by bold lines. The maximum number of channels that can be upgraded is $6$. The cost of upgrading the channels is shown next to the edges (communication channels), and the total cost in the optimal solution is $27$.

The original problem was divided into $13$ Subtasks, but Luogu does not support setting more than $10$ Subtasks. The original problem consisted of $321$ test cases, but Luogu does not support setting more than $100$ test cases. Therefore, this problem only retains the last $100$ test cases and does not use bundled testing.

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

见题面 Input 部分

见题面 Output 部分