Problem A
Fiberoptik

Kommunikationsnätverket i Stackköping består av ett träd med $N$ noder. Du vill välja ut vissa av kanterna och lägga fiberkablar där. Men varje nod kan bara ha högst $K$ kanter med fiberkablar sammankopplade med sig.

Din uppgift är att placera ut så många fiberkablar som möjligt. Men varje kant har också en kostnad, och av alla sätt som finns att lägga ut det maximala antalet fiberkablar, så vill du hitta den minimala möjliga kostnaden.

Indata

Den första raden innehåller två heltal $N$ och $K$ ($2\le N\le {10}^5$, $1\le K\le 100$).

De följande $N-1$ raderna innehåller två heltal $p_i$, $w_i$ ($1\le p_i\le i$, $0\le w_i\le {10}^9$). Detta innebär att det finns en kant mellan noderna med index $p_i$ och $i+1$, med kostnad $w_i$.

Utdata

Skriv ut två heltal, det maximala antalet kanter, och den minimala kostnaden för det antalet kanter.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

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