Thứ tự DFS

Cho một cây có gốc gồm \(n\) đỉnh, đỉnh gốc là đỉnh \(1\). Mỗi đỉnh \(i\) có một trọng số \(w_i\).

Bạn cần tìm một thứ tự duyệt DFS hợp lệ của cây sao cho tổng \(\sum_{i=1}^{n} p_i \cdot w_i\) đạt giá trị lớn nhất, trong đó \(p_i\) là vị trí thăm tương ứng của đỉnh \(i\) trong thứ tự DFS đó (tính từ \(1\)).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(w_1, w_2, \ldots, w_n\) (\(1 \le w_i \le 10^8\)).

• Dòng thứ ba chứa \(n - 1\) số nguyên \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i \le i - 1\)), trong đó \(p_i\) là cha của đỉnh \(i\).

Ràng buộc:

• Subtask 1 (20 số điểm): \(n \le 10\).

• Subtask 2 (40 số điểm): Cây có dạng một đường thẳng (\(p_i = i - 1\)).

• Subtask 3 (40 số điểm): Không có giới hạn gì thêm.

Output

In ra một số nguyên duy nhất là giá trị lớn nhất của \(\sum_{i=1}^{n} p_i \cdot w_i\).

Example

Input:

4
10 100 10 100
1 1 2

Output:

730

Note

Theo thứ tự DFS \((1, 3, 2, 4)\), chúng ta đạt được giá trị lớn nhất: \(1 \times 10 + 2 \times 10 + 3 \times 100 + 4 \times 100 = 730\).