Một trường trung học phổ thông đang triển khai hệ thống học liệu số. Toàn bộ khuôn viên trường được chia thành ~n~ khu vực, được kết nối với nhau theo cấu trúc mạng nội bộ dưới dạng cây có gốc là khu vực trung tâm, đánh số là $1$. Điều đó có nghĩa là giữa các khu vực có đúng ~n-1~ kết nối trực tiếp, toàn bộ hệ thống là liên thông và không có chu trình. Mỗi khu vực đều có đúng một khu vực cha (trừ khu vực trung tâm).

Nhằm đảm bảo phủ sóng học liệu số cho toàn bộ hệ thống, nhà trường cần lắp đặt các thiết bị phát sóng. Một thiết bị được lắp tại một khu vực ~u~ sẽ phủ sóng cho:

• Chính khu vực ~u~.
• Khu vực cha của ~u~ (nếu có).
• Tất cả các khu vực con trực tiếp của ~u~

Mỗi khu vực ~i~ có một chi phí cụ thể ~c_i~ nếu lắp thiết bị phát sóng tại đó.

Hãy giúp nhà trường tìm tổng chi phí nhỏ nhất để phủ sóng toàn bộ hệ thống.

Dữ liệu vào

• Dòng 1: Số nguyên ~n~, là số khu vực (~1 \leq n \leq 10^5~).
• Dòng 2: ~n~ số nguyên ~c_1, c_2, ..., c_n~, là chi phí lắp thiết bị tại từng khu vực (~1 \leq i \leq n~, ~1 \leq c_i \leq 10^6~).
• ~n - 1~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~u~, ~v~ (~1 \leq u, v \leq n~), biểu diễn kết nối trực tiếp giữa hai khu vực.

Dữ liệu ra

Ghi ra một số nguyên duy nhất là tổng chi phí tối thiểu để phủ sóng toàn bộ hệ thống.

Ví dụ

Đầu vào

5
3 2 4 1 5
1 2
1 3
2 4
2 5

Đầu ra

5

Giải thích

Phủ sóng ở hai khu vực ~1~ và ~2~.

Tính điểm

• Subtask 1 ~(50\%)~: ~1 \leq n \leq 20~
• Subtask 2 ~(30\%)~: Luôn tồn tại đường nối giữa đỉnh ~i~ và đỉnh ~i+1~ ~(1 \leq i < n)~.
• Subtask 3 ~(20\%)~: ~1 \leq n \leq 10^5~.