$N$ pastos ($2\le N\le2\cdot10^5$), $N-1$ vias árvore, cada $1$ segundo. Grama inicial $0$, $i$ cresce $a_i$ por segundo ($1\le a_i\le10^8$). John sai $1$, fertiliza todos. Grama $x$ precisa fertilizante $x$, primeira visita apenas, tempo $0$.

Parâmetro $T\in\{0,1\}$.

• $T=0$ fim obrigatório $1$.
• $T=1$ fim qualquer.

Tempo mínimo e fertilizante mínimo para acabar nesse tempo.

Entrada

Primeira $N,T$.

Cada $i=2..N$, linha $p_i,a_i$, via entre $p_i,i$, garante $1\le p_i<i$.

Saída

Tempo mínimo e fertilizante mínimo separados por espaço.

Exemplos

Entrada 1

5 0
1 1
1 2
3 1
3 4

Saída 1

8 21

Nota

Rota ótima:

• Tempo $1$, ir ao nó $3$. grama $1 \cdot 2 = 2$; fertilizante necessário $2$.
• Tempo $2$, ir ao nó $5$. grama $2 \cdot 4 = 8$; fertilizante necessário $8$.
• Tempo $3$, voltar ao nó $3$. Já fertilizado, não precisa novamente.
• Tempo $4$, ir ao nó $4$. grama $4 \cdot 1 = 4$; fertilizante necessário $4$.
• Tempo $5$, voltar ao nó $3$. Já fertilizado, não precisa novamente.
• Tempo $6$, voltar ao nó $1$.
• Tempo $7$, ir ao nó $2$. grama $7 \cdot 1 = 7$; fertilizante necessário $7$.
• Tempo $8$, voltar ao nó $1$.

Tempo $8$, fertilizante $2+8+4+7=21$. Mostra-se mínimo $8$ para voltar $1$, mínimo fertilizante $21$ voltando em $8$.

Entrada 2

5 1
1 1
1 2
3 1
3 4

Saída 2

6 29

Nota

Rota ótima:

• Tempo $1$, ir ao nó $2$. grama $1 \cdot 1 = 1$; fertilizante necessário $1$.
• Tempo $2$, voltar ao nó $1$.
• Tempo $3$, ir ao nó $3$. grama $3 \cdot 2 = 6$; fertilizante necessário $6$.
• Tempo $4$, ir ao nó $5$. grama $4 \cdot 4 = 16$; fertilizante necessário $16$.
• Tempo $5$, voltar ao nó $3$. Já fertilizado, não precisa novamente.
• Tempo $6$, ir ao nó $4$. grama $6 \cdot 1 = 6$; fertilizante necessário $6$.

Tempo $6$, fertilizante $1+6+16+6=29$. Mínimo todas rotas $6$, mínimo fertilizante $29$ nesse tempo.

Subtarefas

• Testes $3..10$: $T=0$.
• Testes $11..22$: $T=1$.
• Testes $3..6$, $11..14$: Nenhum pasto adjacente a mais de três vias.

Créditos: Rohin Garg