$N$ pascoli ($2\le N\le2\cdot10^5$), $N-1$ vie albero, ogni $1$ secondo. Erba iniziale $0$, $i$ cresce $a_i$ al secondo ($1\le a_i\le10^8$). John parte $1$, guida e fertilizza tutti. Erba $x$ richiede $x$ fertilizzante, solo prima visita, tempo $0$.

Parametro $T\in\{0,1\}$.

• $T=0$ fine obbligatoria $1$.
• $T=1$ fine qualsiasi.

Tempo minimo e fertilizzante minimo entro quel tempo.

Input

Prima $N,T$.

Ogni $i=2..N$ riga $p_i,a_i$, via tra $p_i,i$, garantito $1\le p_i<i$.

Output

Tempo e fertilizzante minimi separati da spazio.

Esempi

Input 1

5 0
1 1
1 2
3 1
3 4

Output 1

8 21

Nota

Percorso ottimo:

• Tempo $1$, andare al nodo $3$. erba $1 \cdot 2 = 2$; fertilizzante necessario $2$.
• Tempo $2$, andare al nodo $5$. erba $2 \cdot 4 = 8$; fertilizzante necessario $8$.
• Tempo $3$, tornare al nodo $3$. Già fertilizzato, non serve di nuovo.
• Tempo $4$, andare al nodo $4$. erba $4 \cdot 1 = 4$; fertilizzante necessario $4$.
• Tempo $5$, tornare al nodo $3$. Già fertilizzato, non serve di nuovo.
• Tempo $6$, tornare al nodo $1$.
• Tempo $7$, andare al nodo $2$. erba $7 \cdot 1 = 7$; fertilizzante necessario $7$.
• Tempo $8$, tornare al nodo $1$.

Tempo $8$, fertilizzante $2+8+4+7=21$. Si mostra minimo $8$ per tornare $1$, fertilizzante minimo $21$ tornando in $8$.

Input 2

5 1
1 1
1 2
3 1
3 4

Output 2

6 29

Nota

Percorso ottimo:

• Tempo $1$, andare al nodo $2$. erba $1 \cdot 1 = 1$; fertilizzante necessario $1$.
• Tempo $2$, tornare al nodo $1$.
• Tempo $3$, andare al nodo $3$. erba $3 \cdot 2 = 6$; fertilizzante necessario $6$.
• Tempo $4$, andare al nodo $5$. erba $4 \cdot 4 = 16$; fertilizzante necessario $16$.
• Tempo $5$, tornare al nodo $3$. Già fertilizzato, non serve di nuovo.
• Tempo $6$, andare al nodo $4$. erba $6 \cdot 1 = 6$; fertilizzante necessario $6$.

Tempo $6$, fertilizzante $1+6+16+6=29$. Minimo ogni percorso $6$, fertilizzante minimo $29$ con $6$.

Sottoproblemi

• Test $3..10$: $T=0$.
• Test $11..22$: $T=1$.
• Test $3..6$, $11..14$: Nessun pascolo adiacente a più di tre vie.

Crediti: Rohin Garg