\(N\)개의 초원이 \(N-1\)개의 길로 연결되어 트리를 이룬다. \((2 \le N \le 2 \times 10^5)\) 각 길을 건너는 데에는 \(1\)초가 걸린다.

처음에 모든 초원에는 풀이 없다. \(i\)번째 초원의 풀은 초당 \(a_i\)만큼 자란다. \((1 \le a_i \le 10^8)\) 존은 처음에 \(1\)번 초원에 있으며, 모든 초원을 돌아다니며 풀에 비료를 주어야 한다. 풀이 \(x\)만큼 자란 초원에 방문하면 비료가 \(x\)만큼 필요하다. 각 초원에는 처음 방문했을 때에만 비료를 주며, 비료를 주는 데에는 시간이 걸리지 않는다.

입력으로 매개변수 \(T \in \{0,1\}\)도 함께 주어진다.

• \(T=0\)이면 존은 마지막에 \(1\)번 초원으로 돌아와야 한다.
• \(T=1\)이면 존은 어느 초원에서든 이동을 끝낼 수 있다.

모든 초원에 비료를 주는 데 걸리는 시간의 최솟값과, 그 최소 시간 안에 모든 초원에 비료를 줄 때 필요한 비료 양의 최솟값을 구하여라.

입력

첫째 줄에 \(N\)과 \(T\)가 공백으로 구분되어 주어진다.

각 \(i=2,3,\dots,N\)에 대하여 한 줄에 \(p_i\)와 \(a_i\)가 주어진다. 이는 \(p_i\)번 초원과 \(i\)번 초원을 연결하는 길이 있으며, \(i\)번 초원의 풀은 초당 \(a_i\)만큼 자란다는 뜻이다.

항상 \(1 \le p_i<i\)를 만족한다.

출력

모든 초원에 비료를 주는 데 걸리는 최소 시간과, 그 시간 안에 필요한 비료 양의 최솟값을 공백으로 구분하여 출력한다.

예제 입력 1

5 0
1 1
1 2
3 1
3 4

예제 출력 1

8 21

예제 설명 1

존의 최적 이동 경로는 다음과 같다.

• 시각 \(1\)에 \(3\)번 초원으로 이동한다. 풀이 \(1 \times 2=2\)만큼 자랐으므로 비료가 \(2\)만큼 필요하다.
• 시각 \(2\)에 \(5\)번 초원으로 이동한다. 풀이 \(2 \times 4=8\)만큼 자랐으므로 비료가 \(8\)만큼 필요하다.
• 시각 \(3\)에 \(3\)번 초원으로 돌아간다. 이미 비료를 주었으므로 다시 비료를 줄 필요는 없다.
• 시각 \(4\)에 \(4\)번 초원으로 이동한다. 풀이 \(4 \times 1=4\)만큼 자랐으므로 비료가 \(4\)만큼 필요하다.
• 시각 \(5\)에 이미 비료를 준 \(3\)번 초원으로 돌아간다.
• 시각 \(6\)에 \(1\)번 초원으로 돌아간다.
• 시각 \(7\)에 \(2\)번 초원으로 이동한다. 풀이 \(7 \times 1=7\)만큼 자랐으므로 비료가 \(7\)만큼 필요하다.
• 시각 \(8\)에 \(1\)번 초원으로 돌아간다.

이 경로에는 \(8\)의 시간이 걸리고 비료가 \(2+8+4+7=21\)만큼 필요하다. 마지막에 \(1\)번 초원으로 돌아오는 모든 경로 중 걸리는 시간의 최솟값이 \(8\)이며, 그러한 경로 중 필요한 비료 양의 최솟값이 \(21\)임을 보일 수 있다.

예제 입력 2

5 1
1 1
1 2
3 1
3 4

예제 출력 2

6 29

예제 설명 2

존의 최적 이동 경로는 다음과 같다.

• 시각 \(1\)에 \(2\)번 초원으로 이동한다. 풀이 \(1 \times 1=1\)만큼 자랐으므로 비료가 \(1\)만큼 필요하다.
• 시각 \(2\)에 \(1\)번 초원으로 돌아간다.
• 시각 \(3\)에 \(3\)번 초원으로 이동한다. 풀이 \(3 \times 2=6\)만큼 자랐으므로 비료가 \(6\)만큼 필요하다.
• 시각 \(4\)에 \(5\)번 초원으로 이동한다. 풀이 \(4 \times 4=16\)만큼 자랐으므로 비료가 \(16\)만큼 필요하다.
• 시각 \(5\)에 이미 비료를 준 \(3\)번 초원으로 돌아간다.
• 시각 \(6\)에 \(4\)번 초원으로 이동한다. 풀이 \(6 \times 1=6\)만큼 자랐으므로 비료가 \(6\)만큼 필요하다.

이 경로에는 \(6\)의 시간이 걸리고 비료가 \(1+6+16+6=29\)만큼 필요하다. 모든 경로 중 걸리는 시간의 최솟값이 \(6\)이며, 그러한 경로 중 필요한 비료 양의 최솟값이 \(29\)임을 보일 수 있다.

출처

USACO 2023 February Contest, Gold, Problem 2. Fertilizing Pastures