$N$ ruộng ($2\le N\le2\cdot10^5$), $N-1$ đường cây, mỗi $1$ giây. Cỏ đầu $0$, $i$ lớn $a_i$ mỗi giây ($1\le a_i\le10^8$). John đầu $1$, lái bón hết. Cỏ $x$ cần phân $x$, lần thăm đầu thôi, thời gian $0$.

Tham số $T\in\{0,1\}$.

• $T=0$ phải kết $1$.
• $T=1$ kết bất kỳ.

Thời gian ít nhất và phân ít nhất trong thời gian đó.

Dữ liệu vào

Đầu $N,T$.

Mỗi $i=2..N$ dòng $p_i,a_i$, đường giữa $p_i,i$, bảo đảm $1\le p_i<i$.

Dữ liệu ra

Thời gian và phân ít nhất cách trắng.

Ví dụ

Dữ liệu vào 1

5 0
1 1
1 2
3 1
3 4

Dữ liệu ra 1

8 21

Ghi chú

Đường tối ưu:

• Thời gian $1$, đến nút $3$. cỏ $1 \cdot 2 = 2$; phân cần $2$.
• Thời gian $2$, đến nút $5$. cỏ $2 \cdot 4 = 8$; phân cần $8$.
• Thời gian $3$, về nút $3$. Đã bón, không cần lại.
• Thời gian $4$, đến nút $4$. cỏ $4 \cdot 1 = 4$; phân cần $4$.
• Thời gian $5$, về nút $3$. Đã bón, không cần lại.
• Thời gian $6$, về nút $1$.
• Thời gian $7$, đến nút $2$. cỏ $7 \cdot 1 = 7$; phân cần $7$.
• Thời gian $8$, về nút $1$.

Thời gian $8$, phân $2+8+4+7=21$. Chứng minh về $1$ ít nhất $8$, về trong $8$ ít phân nhất $21$.

Dữ liệu vào 2

5 1
1 1
1 2
3 1
3 4

Dữ liệu ra 2

6 29

Ghi chú

Đường tối ưu:

• Thời gian $1$, đến nút $2$. cỏ $1 \cdot 1 = 1$; phân cần $1$.
• Thời gian $2$, về nút $1$.
• Thời gian $3$, đến nút $3$. cỏ $3 \cdot 2 = 6$; phân cần $6$.
• Thời gian $4$, đến nút $5$. cỏ $4 \cdot 4 = 16$; phân cần $16$.
• Thời gian $5$, về nút $3$. Đã bón, không cần lại.
• Thời gian $6$, đến nút $4$. cỏ $6 \cdot 1 = 6$; phân cần $6$.

Thời gian $6$, phân $1+6+16+6=29$. Mọi đường ít nhất $6$, trong $6$ ít phân nhất $29$.

Nhiệm vụ con

• Kiểm thử $3..10$: $T=0$.
• Kiểm thử $11..22$: $T=1$.
• Kiểm thử $3..6$, $11..14$: Không ruộng kề quá ba đường.

Ghi công: Rohin Garg