Tô màu cây

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 cần tìm cách tô màu cho tất cả các đỉnh.

Thao tác tô màu được định nghĩa như sau: Chọn một đỉnh \(u\) và tô tất cả các đỉnh \(v\) thành màu đen nếu thỏa mãn các điều kiện sau:

• Đỉnh \(v\) nằm trong cây con gốc \(u\).
• Khoảng cách giữa hai đỉnh \(u\) và \(v\) chính xác là \(i\). (Khoảng cách được định nghĩa là số cạnh ngắn nhất để đi từ \(u\) đến \(v\).)

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

Yêu cầu: Hãy tìm cách tô màu sao cho tất cả các đỉnh đều trở thành màu đen với tổng chi phí nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)).
• Dòng thứ hai gồm \(n\) số \(c_0, c_1, \dots, c_{n-1}\) (\(c_i \leq 10^9\)), với \(c_i\) là chi phí để tô màu ở khoảng cách \(i\).
• Dòng thứ ba gồm \(n\) số \(a_1, a_2, \dots, a_n\). Nếu \(a_i = 0\) thì đỉnh \(i\) chưa được tô màu, nếu \(a_i = 1\) thì đỉnh \(i\) đã được tô màu.
• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u, v\) mô tả một cạnh của cây.

Output

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

Example

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

11

Scoring

• Có 20% số test với \(n \leq 20\).
• Có 30% số test với \(n \leq 200\).
• Có 30% số test với \(n \leq 2000\).
• Số test còn lại không có ràng buộc gì thêm.