Cho một cây có ~n~ đỉnh. Các đỉnh được đánh số từ ~1~ đến ~n~ và gốc của cây là đỉnh ~1~. Một số đỉnh của cây đã được tô màu đen, một số khác thì chưa được tô màu. Ta sẽ tìm cách tô màu cho tất cả các đỉnh.

Thao tác tô màu sẽ được thực hiện như sau: Chọn một đỉnh ~u~ và tô tất cả các đỉnh ~v~ thành màu đen nếu các điều kiện sau thỏa mãn:

• Đỉnh ~v~ nằm trong cây con gốc ~u~.

• Khoảng cách giữa hai đỉnh chính xác là ~i~. Trong đó khoảng cách giữa hai đỉnh ~u~ và ~v~ là số cạnh nhỏ nhất để đi từ ~u~ đến ~v~.

Chi phí để tô màu một đỉnh có khoảng cách ~i~ là ~c_i~. Tại một thao tác tô màu, nếu chọn đỉnh ~u~ mà có nhiều hơn một đỉnh ~v~ cùng có khoảng cách với đỉnh ~u~ bằng ~i~ thì các đỉnh này sẽ được tô màu cùng lúc với chi phí là ~c_i~.

Yêu cầu: Tìm cách tô sao cho tất cả các đỉnh đều được tô thành màu đen với chi phí là nhỏ nhất.

Input

• Dòng đầu chứa ~n~ ~(1 \le n \le 10^6)~.

• Dòng tiếp theo gồm ~n~ số ~c_0,c_1,\dots,c_{n-1}~ ~(c_i \le 10^9)~, với ~c_i~ là chi phí để tô màu ở khoảng cách ~i~.

• Dòng tiếp theo gồm ~n~ số ~a_1,a_2,\dots,a_n~. Trong đó ~a_i=0/1~. Nếu ~a_i=0~ tương ứng là đỉnh ~i~ chưa được tô màu, ~a_i=1~ là đỉnh đã được tô màu.

• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số ~u,v~ thể hiện một cạnh của cây.

Output

Một dòng ghi một số là tổng chi phí để tô tất cả các nút thành màu đen.

Scoring

Sample Input 1

5
10 5 1 5 5
0 1 0 0 1
1 2
2 3
2 4
4 5

Sample Output 1

11

Notes

• Chọn đỉnh ~1~ làm gốc, tô màu đỉnh ~3~ và ~4~ với khoảng cách ~2~, chi phí ~1~.

• Sau đó tô đỉnh ~1~ với khoảng cách ~0~, chi phí ~10~.