$N$ pastos ($2\le N\le2\cdot10^5$), $N-1$ vías árbol, cada $1$ segundo. Hierba inicial $0$, $i$ crece $a_i$ por segundo ($1\le a_i\le10^8$). John sale $1$, fertiliza todos. Hierba $x$ requiere fertilizante $x$, primera visita solo, tiempo $0$.

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

• $T=0$ fin obligatorio $1$.
• $T=1$ fin cualquiera.

Mínimo tiempo y mínimo fertilizante para acabar en ese tiempo.

Entrada

Primera $N,T$.

Cada $i=2..N$, línea $p_i,a_i$, vía entre $p_i,i$, garantiza $1\le p_i<i$.

Salida

Tiempo mínimo y fertilizante mínimo separados por espacio.

Ejemplos

Entrada 1

5 0
1 1
1 2
3 1
3 4

Salida 1

8 21

Nota

Ruta óptima:

• Tiempo $1$, ir al nodo $3$. hierba $1 \cdot 2 = 2$; fertilizante necesario $2$.
• Tiempo $2$, ir al nodo $5$. hierba $2 \cdot 4 = 8$; fertilizante necesario $8$.
• Tiempo $3$, volver al nodo $3$. Ya fertilizado, no hace falta otra vez.
• Tiempo $4$, ir al nodo $4$. hierba $4 \cdot 1 = 4$; fertilizante necesario $4$.
• Tiempo $5$, volver al nodo $3$. Ya fertilizado, no hace falta otra vez.
• Tiempo $6$, volver al nodo $1$.
• Tiempo $7$, ir al nodo $2$. hierba $7 \cdot 1 = 7$; fertilizante necesario $7$.
• Tiempo $8$, volver al nodo $1$.

Tiempo $8$, fertilizante $2+8+4+7=21$. Se muestra mínimo $8$ para volver $1$, mínimo fertilizante $21$ al volver en $8$.

Entrada 2

5 1
1 1
1 2
3 1
3 4

Salida 2

6 29

Nota

Ruta óptima:

• Tiempo $1$, ir al nodo $2$. hierba $1 \cdot 1 = 1$; fertilizante necesario $1$.
• Tiempo $2$, volver al nodo $1$.
• Tiempo $3$, ir al nodo $3$. hierba $3 \cdot 2 = 6$; fertilizante necesario $6$.
• Tiempo $4$, ir al nodo $5$. hierba $4 \cdot 4 = 16$; fertilizante necesario $16$.
• Tiempo $5$, volver al nodo $3$. Ya fertilizado, no hace falta otra vez.
• Tiempo $6$, ir al nodo $4$. hierba $6 \cdot 1 = 6$; fertilizante necesario $6$.

Tiempo $6$, fertilizante $1+6+16+6=29$. Mínimo todas rutas $6$, mínimo fertilizante $29$ en ese tiempo.

Subtareas

• Pruebas $3..10$: $T=0$.
• Pruebas $11..22$: $T=1$.
• Pruebas $3..6$, $11..14$: Ningún pasto adyacente a más de tres vías.

Créditos: Rohin Garg