$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