Охоронець Антон

Антон працює охоронцем. Він відповідає за $n$ об'єктів, які пронумеровані цілими числами від $1$ до $n$. Також є $n-1$ дорога. $i$-та дорога з'єднує об'єкти $u_i$ та $v_i$, а також має довжину $w_i$. З кожного об'єкту можна дістатися до об'єкта $1$.

На початку Антон знаходиться в об'єкті $1$.

Визначимо пріоритетність кожного об'єкта, як мінімальну кількість доріг, яку потрібно пройти від цього об'єкта до об'єкта $1$. Наприклад, для об'єкта $1$ це число буде $0$; для всіх об'єктів, які напряму з'єднані з $1$ — це буде $1$; і так далі.

Антону потрібно зробити обхід всіх об'єктів. Йому потрібно спочатку відвідати усі об'єкти, які мають пріоритетність $1$, потім, які мають пріоритетність $2$, і так далі. Якщо є кілька об'єктів з однаковою пріоритетністю, то Антон може самостійно вибирати у якому порядку їх відвідувати. Зверніть увагу, що відвідувати будь-який об'єкт з пріоритетом $k$ він може лише, якщо відвідав усі об'єкти з пріоритетом $k-1$.

Знайдіть мінімальну відстань, яку йому прийдеться пройти.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^6$).

Другий рядок містить $n-1$ цілих чисел $p_i$, які показують, що є дорога від об'єкта $i+1$ до об'єкта $p_i$ ($1\le p_i\le n$);

Третій рядок містить $n-1$ цілих чисел $w_i$, які є довжинами доріг між об'єктами $i+1$ та $p_i$ ($1\le w_i\le 10^9$).

Гарантується, що з об'єкта $1$ можна дійти до всіх інших об'єктів.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Оцінювання

1. ($4$ бали): $1\le n\le 10$;

2. ($5$ балів): $1\le n\le 22$;

3. ($13$ балів): не більше $6$ об'єктів мають однакову пріоритетність;

4. ($10$ балів): не більше $10$ об'єктів мають однакову пріоритетність;

5. ($15$ балів): $w_i=1$;

6. ($15$ балів): $1\le n\le 10^5$;

7. ($38$ балів): без додаткових обмежень.