Optical Communication Channels

Flatland has $n$ cities numbered from 1 to $n$. City 1 is the capital. Each city has one connection center, and centers can be linked to other centers by wired communication channels. Any two cities are joined by exactly one route through the channels, so the network is a tree. For a city $i$ with $i > 1$, let $p_i$ be the first city on the route from city $i$ to the capital.

The network is being upgraded, and some wired channels will be replaced with newer optical ones. An optical channel can only be installed in place of an existing wired channel. Replacing the channel that connects city $i$ with city $p_i$ costs $w_i$. Because of technology limits, each connection center can be connected by optical channels to at most $k$ other centers.

The Flatland ministry wants a plan that makes the optical network as connected as possible, so it must upgrade as many channels as it can. Among plans with the same number of upgraded channels, the total cost should be minimal.

Help the ministry choose the channels to upgrade.

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le 100$). Each of the next $n - 1$ lines contains two integers $p_i$ and $w_i$ ($1 \le p_i \le i$, $0 \le w_i \le 10^9$). The $(i-1)$-th of these lines describes city $i$.

Print two integers $cnt$ and $cost$: the maximum number of channels that can be upgraded, and the minimum cost of upgrading that many channels.

In the first example, the network before and after the upgrade is shown in the figure below. Upgraded channels are drawn as thick lines. The maximum number of channels that can be upgraded is 4. The upgrade cost of every channel is 0, so costs are not shown.

There are other valid solutions that upgrade 4 channels.

In the second example, the network before and after the upgrade is shown below. Upgraded channels are thick lines, and the cost of each channel is written next to it. The maximum number of upgraded channels is 6, and the total cost of the optimal solution is 27.