Bón Phân Đồng Cỏ

Có $N$ đồng cỏ được nối bởi $N-1$ con đường tạo thành một cây. Mỗi con đường tốn 1 giây để đi qua. Đồng cỏ $i$ có cỏ mọc với tốc độ $a_i$ đơn vị/giây (ban đầu tất cả bằng 0). Nông dân John bắt đầu tại đồng cỏ 1 và phải thăm tất cả các đồng cỏ để bón phân. Khi đến đồng cỏ có $x$ đơn vị cỏ, anh cần $x$ đơn vị phân bón (chỉ cần bón lần đầu thăm).

Tham số $T$ xác định FJ phải quay về đồng cỏ 1 ($T=0$) hay được kết thúc ở bất kỳ đâu ($T=1$).

Hãy tìm thời gian tối thiểu và lượng phân bón tối thiểu cho thời gian đó.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $T$ ($2\le N\le 2·{10}^5$, $T\in \{0,1\}$).
• Dòng $i$ ($2\le i\le N$): Hai số nguyên $p_i$ và $a_i$ ($1\le p_i<i$, $1\le a_i\le {10}^8$) — cha của đỉnh $i$ và tốc độ mọc cỏ.

Dữ liệu ra

Hai số nguyên cách nhau bởi dấu cách: thời gian tối thiểu và lượng phân bón tối thiểu cho thời gian đó.

Ràng buộc

• $2\le N\le 2·{10}^5$
• $T\in \{0,1\}$
• $1\le a_i\le {10}^8$

Ví dụ