$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$、その時間なら最小肥料 $29$。

小課題

• テスト $3..10$: $T=0$.
• テスト $11..22$: $T=1$.
• テスト $3..6$, $11..14$: 隣接道路三本を超える牧草地なし。

問題のクレジット：Rohin Garg