$N$ пастбищ ($2\le N\le2\cdot10^5$), $N-1$ дорог дерево, каждая $1$ секунда. Изначально трава $0$, у $i$ растёт $a_i$ в секунду ($1\le a_i\le10^8$). John в $1$, едет удобрять все. При траве $x$ нужно $x$ удобрения, только первый визит, $0$ времени.

Параметр $T\in\{0,1\}$.

• $T=0$ финиш обязательно $1$.
• $T=1$ финиш любой.

Минимальное время и минимальное удобрение среди маршрутов этого времени.

Входные данные

Первая $N,T$.

Для $i=2..N$ строка $p_i,a_i$, дорога между $p_i,i$, гарантировано $1\le p_i<i$.

Выходные данные

Минимальное время и удобрение через пробел.

Примеры

Входные данные 1

5 0
1 1
1 2
3 1
3 4

Выходные данные 1

8 21

Примечание

Оптимальный маршрут:

• Время $1$, перейти в узел $3$. трава $1 \cdot 2 = 2$; нужно удобрение $2$.
• Время $2$, перейти в узел $5$. трава $2 \cdot 4 = 8$; нужно удобрение $8$.
• Время $3$, вернуться в узел $3$. Уже удобрено, повторно не нужно.
• Время $4$, перейти в узел $4$. трава $4 \cdot 1 = 4$; нужно удобрение $4$.
• Время $5$, вернуться в узел $3$. Уже удобрено, повторно не нужно.
• Время $6$, вернуться в узел $1$.
• Время $7$, перейти в узел $2$. трава $7 \cdot 1 = 7$; нужно удобрение $7$.
• Время $8$, вернуться в узел $1$.

Время $8$, удобрение $2+8+4+7=21$. Можно доказать: возврат в $1$ минимум $8$, при возврате за $8$ удобрение минимум $21$.

Входные данные 2

5 1
1 1
1 2
3 1
3 4

Выходные данные 2

6 29

Примечание

Оптимальный маршрут:

• Время $1$, перейти в узел $2$. трава $1 \cdot 1 = 1$; нужно удобрение $1$.
• Время $2$, вернуться в узел $1$.
• Время $3$, перейти в узел $3$. трава $3 \cdot 2 = 6$; нужно удобрение $6$.
• Время $4$, перейти в узел $5$. трава $4 \cdot 4 = 16$; нужно удобрение $16$.
• Время $5$, вернуться в узел $3$. Уже удобрено, повторно не нужно.
• Время $6$, перейти в узел $4$. трава $6 \cdot 1 = 6$; нужно удобрение $6$.

Время $6$, удобрение $1+6+16+6=29$. Минимум времени всех маршрутов $6$, при $6$ минимум удобрения $29$.

Подзадачи

• Тесты $3..10$: $T=0$.
• Тесты $11..22$: $T=1$.
• Тесты $3..6$, $11..14$: Нет пастбища с более чем тремя дорогами.

Авторство: Rohin Garg