$N$ Weiden ($2\le N\le2\cdot10^5$), $N-1$ Straßen Baum, je $1$ Sekunde. Gras anfangs $0$, $i$ wächst $a_i$ pro Sekunde ($1\le a_i\le10^8$). John startet $1$, fährt alle düngen. Gras $x$ braucht Dünger $x$, nur erster Besuch, $0$ Zeit.

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

• $T=0$ Ende zwingend $1$.
• $T=1$ beliebiges Ende.

Minimale Zeit und minimaler Dünger innerhalb dieser Zeit.

Eingabe

Erste $N,T$.

Je $i=2..N$ Zeile $p_i,a_i$, Straße zwischen $p_i,i$, garantiert $1\le p_i<i$.

Ausgabe

Minimale Zeit und Dünger mit Leerzeichen.

Beispiele

Eingabe 1

5 0
1 1
1 2
3 1
3 4

Ausgabe 1

8 21

Hinweis

Optimaler Weg:

• Zeit $1$, zum Knoten gehen $3$. Gras $1 \cdot 2 = 2$; nötiger Dünger $2$.
• Zeit $2$, zum Knoten gehen $5$. Gras $2 \cdot 4 = 8$; nötiger Dünger $8$.
• Zeit $3$, zum Knoten zurück $3$. Schon gedüngt, nicht erneut nötig.
• Zeit $4$, zum Knoten gehen $4$. Gras $4 \cdot 1 = 4$; nötiger Dünger $4$.
• Zeit $5$, zum Knoten zurück $3$. Schon gedüngt, nicht erneut nötig.
• Zeit $6$, zum Knoten zurück $1$.
• Zeit $7$, zum Knoten gehen $2$. Gras $7 \cdot 1 = 7$; nötiger Dünger $7$.
• Zeit $8$, zum Knoten zurück $1$.

Zeit $8$, Dünger $2+8+4+7=21$. Beweisbar minimale Rückkehrzeit zu $1$ ist $8$, minimaler Dünger bei Rückkehr in $8$ ist $21$.

Eingabe 2

5 1
1 1
1 2
3 1
3 4

Ausgabe 2

6 29

Hinweis

Optimaler Weg:

• Zeit $1$, zum Knoten gehen $2$. Gras $1 \cdot 1 = 1$; nötiger Dünger $1$.
• Zeit $2$, zum Knoten zurück $1$.
• Zeit $3$, zum Knoten gehen $3$. Gras $3 \cdot 2 = 6$; nötiger Dünger $6$.
• Zeit $4$, zum Knoten gehen $5$. Gras $4 \cdot 4 = 16$; nötiger Dünger $16$.
• Zeit $5$, zum Knoten zurück $3$. Schon gedüngt, nicht erneut nötig.
• Zeit $6$, zum Knoten gehen $4$. Gras $6 \cdot 1 = 6$; nötiger Dünger $6$.

Zeit $6$, Dünger $1+6+16+6=29$. Alle Wege minimal $6$, Dünger bei $6$ minimal $29$.

Teilaufgaben

• Tests $3..10$: $T=0$.
• Tests $11..22$: $T=1$.
• Tests $3..6$, $11..14$: Keine Weide an mehr als drei Straßen.

Credits: Rohin Garg