$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说明
John 最优路线如下：
- 时刻 $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$，而回 $1$ 且耗 $8$ 的路线最少肥 $21$。
输入格式 2
5 1
1 1
1 2
3 1
3 4输出格式 2
6 29说明
John 最优路线如下：
- 时刻 $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