$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