Problem Description

For a weighted tree $T$ with $n$ nodes, define $dis(x,y)$ as the sum of edge weights on the path $x\to y$ in $T$. Then define an undirected complete graph $p(T)=G$ with $n$ nodes, where for all $x,y\in [1,n]$, the weight of edge $(x,y)$ in $G$ is $dis(x,y)$.

Define $f(T)$ as the maximum spanning tree of $p(T)$. In particular, if the maximum spanning tree of $p(T)$ is not unique, you must determine it immediately and report it.

Given a tree $T_0$ and an integer $k$, find $f^k(T_0)$. Its definition is given below.

Input Format

The first line contains two integers $n,k$.
In the next lines $2\sim n$, line $i$ contains two integers $i-f_i,v_i$, representing an edge $(i,f_i)$ of $T_0$ with weight $v_i$. That is, this line inputs two integers $f'_i,v_i$, and the real $f_i=i-f'_i$.

Output Format

Output only one integer as the answer.

If $\exists x\in[0,k-1]$ such that the maximum spanning tree of $p(f^x(T_0))$ is not unique, output $-1$. Otherwise, output the sum of all edge weights of $f^k(T_0)$ modulo $2^{32}$.

3 3
1 1
2 2

13

10 2
1 7
1 2
1 5
4 5
2 1
3 9
2 9
4 4
9 4

736

4 1
1 1
2 1
3 1

-1

Hint

Definition

The definition of $f^k(T)$ is:

$$f^k(T)=\begin{cases}T&k=0\\f(f^{k-1}(T))&k>0\end{cases}$$

Explanation for Sample $1$

They are $T_0,f(T_0),f^2(T_0),f^3(T_0)$.

Take the process of computing $f(T_0)$ as an example. The generated $p(T_0)=G$ is

The edges in the maximum spanning tree are $(1,3),(2,3)$.

Constraints

This problem uses bundled testdata.

$\text{Subtask}$	$n\le$	$k\le$	$\text{Score}$
$1$	$10^3$	$1$	$10$
$2$	$10^5$		$20$
$3$	$10^6$		$30$
$4$		$10^7$	$40$

For $100\%$ of the data, $2\le n\le 10^6$, $1\le k\le 10^7$, $1\le f_i<i$, $1\le v_i\le10^9$.

Special Scoring Method

This problem enables subtask dependency, as follows:

• For subtask $i$, you need to solve all subtasks $j\in[1,i]$ to get the score of subtask $i$.

Translated by ChatGPT 5