Cho đồ thị dạng cây gồm N đỉnh, các đỉnh được đánh số từ 1 đến N,mỗi đỉnh 𝑣 được gán một số nguyên dương 𝑎𝑣. Gọi 𝑑𝑖𝑠(𝑥, 𝑦) là khoảng cách giữa 2 đỉnh 𝑥, 𝑦, khoảng cách được tính bằng số cạnh trên đường đi đơn từ 𝑥 đến 𝑦. Mỗi khi chọn một đỉnh 𝑣 bất kì làm gốc thì ta thu được tổng giá trị của cây là:

dist(v,1)x a[1]+ dist(v,2) x a[2] + … + dist(v,n) x a[n].

Hãy tìm giá trị lớn nhất có thể của cây.

Input:

• Dòng đầu tiên là số 𝑁 là số đỉnh của đồ thị.

• Dòng tiếp theo ghi 𝑁 số nguyên dương 𝑎1, 𝑎2, … 𝑎𝑁 là các số được gán với 𝑁 đỉnh theo thứ tự.

• Dòng tiếp theo có 𝑁 số 𝑝1, 𝑝2, . . 𝑝𝑁 thể hiện có đường đi từ đỉnh 𝑖 đến 𝑝𝑖, 𝑝𝑖 = 0 thì đỉnh 𝑖 là đỉnh gốc ban đầu, còn lại 1 ≤ 𝑝𝑖 ≤ 𝑁.

Output:

Một số duy nhất là giá trị lớn nhất có thể của cây.

Ràng buộc:

𝑁 ≤ 200000, 1 ≤ 𝑎𝑖 ≤ 200000.

Sample Input

14

3 2 1 10 1 3 9 1 5 3 4 5 9 8

0 1 1 1 2 2 3 4 4 4 5 5 7 7

Sample Output

269

Sample Input

8

9 4 1 7 10 1 6 5

0 1 2 1 1 5 5 5

Sample Output

121