$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