Є \(N\) пасовищ (\(2 \le N \le 2\cdot 10^5\)), з'єднаних \(N-1\) дорогою, так що вони утворюють дерево. Переміщення кожною дорогою займає одну секунду. На початку на кожному пасовищі 0 трави, трава на \(i\)-му пасовищі росте зі швидкістю \(a_i\) (\(1\le a_i\le 10^8\)) одиниць за секунду. Фермер Джон спочатку знаходиться в пасовищі. і повинен удобрити траву на кожному пасовищі. Якщо він відвідує пасовище, в якому \(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\).

Формат вихідних даних

Мінімальну кількість часу та мінімальну кількість добрив, розділені пропуском.

Приклад вхідних даних

5 0
1 1
1 2
3 1
3 4

Приклад вихідних даних

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\) добрив. Можна показати, що \(8\) - це мінімальна кількість часу для будь-якого маршруту, який повернеться у вершину \(1\) наприкінці, а \(21\) - це мінімальна кількість добрив серед усіх маршрутів, які повернуться у вершину \(1\) за \(8\) одиниць часу.

Приклад вхідних даних

5 1
1 1
1 2
3 1
3 4

Приклад вихідних даних

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\) добрив. Можна показати, що це мінімальна кількість часу для будь-якого маршруту і ~29

• мінімальна кількість добрив, яка витратиться серед усіх маршрутів, що займають \(6\) одиниць часу.

ОЦІНЮВАННЯ:

• У тестах 3-10: \(T=0\)
• У тестах 11-22: \(T=1\)
• У тестах 3-6 та 11-14: Немає пасовищ, з яких виходить більш ніж 3 дороги.