$N$ pastwisk ($2\le N\le2\cdot10^5$), $N-1$ dróg drzewo, każda $1$ sekunda. Trawa początkowa $0$, $i$ rośnie $a_i$ na sekundę ($1\le a_i\le10^8$). John w $1$, jeździ nawozić wszystkie. Trawa $x$ wymaga nawozu $x$, pierwszy raz tylko, czas $0$.

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

• $T=0$ koniec koniecznie $1$.
• $T=1$ dowolny koniec.

Minimalny czas i minimalny nawóz kończąc w tym czasie.

Wejście

Pierwszy $N,T$.

Dla $i=2..N$ wiersz $p_i,a_i$, droga między $p_i,i$, gwarancja $1\le p_i<i$.

Wyjście

Minimalny czas i nawóz spacją.

Przykład

Wejście 1

5 0
1 1
1 2
3 1
3 4

Wyjście 1

8 21

Uwagi

Optymalna trasa:

• Czas $1$, idź do węzła $3$. trawa $1 \cdot 2 = 2$; potrzebny nawóz $2$.
• Czas $2$, idź do węzła $5$. trawa $2 \cdot 4 = 8$; potrzebny nawóz $8$.
• Czas $3$, wróć do węzła $3$. Już nawożone, nie ponownie.
• Czas $4$, idź do węzła $4$. trawa $4 \cdot 1 = 4$; potrzebny nawóz $4$.
• Czas $5$, wróć do węzła $3$. Już nawożone, nie ponownie.
• Czas $6$, wróć do węzła $1$.
• Czas $7$, idź do węzła $2$. trawa $7 \cdot 1 = 7$; potrzebny nawóz $7$.
• Czas $8$, wróć do węzła $1$.

Czas $8$, nawóz $2+8+4+7=21$. Dowodliwy minimalny powrót $1$ w $8$, nawóz minimum $21$ wracając w $8$.

Wejście 2

5 1
1 1
1 2
3 1
3 4

Wyjście 2

6 29

Uwagi

Optymalna trasa:

• Czas $1$, idź do węzła $2$. trawa $1 \cdot 1 = 1$; potrzebny nawóz $1$.
• Czas $2$, wróć do węzła $1$.
• Czas $3$, idź do węzła $3$. trawa $3 \cdot 2 = 6$; potrzebny nawóz $6$.
• Czas $4$, idź do węzła $5$. trawa $4 \cdot 4 = 16$; potrzebny nawóz $16$.
• Czas $5$, wróć do węzła $3$. Już nawożone, nie ponownie.
• Czas $6$, idź do węzła $4$. trawa $6 \cdot 1 = 6$; potrzebny nawóz $6$.

Czas $6$, nawóz $1+6+16+6=29$. Wszystkie trasy minimum $6$, przy $6$ nawóz minimum $29$.

Podzadania

• Testy $3..10$: $T=0$.
• Testy $11..22$: $T=1$.
• Testy $3..6$, $11..14$: Żadne pastwisko nie sąsiaduje z ponad trzema drogami.

Autorstwo: Rohin Garg