Người giao hàng

Ở một quốc gia nọ có $N$ hòn đảo, được đánh số lần lượt từ $1$ đến $N$. Có $N-1$ cây cầu, mỗi cây cầu nối trực tiếp $2$ hòn đảo tạo thành một quần thể đảo mà giữa hai hòn đảo bất kỳ luôn tồn tại đường đi thông qua một cây cầu hoặc một dãy các cây cầu.

Tuấn là một người giao hàng của công ty VOI. Ban đầu Tuấn ở hòn đảo $1$, được giao $K$ nhiệm vụ giao hàng theo thứ tự từ $1$ đến $K$ và Tuấn phải xử lý các nhiệm vụ theo đúng thứ tự đó. Với nhiệm vụ thứ $i$ ($1\le i\le K$), Tuấn cần thực hiện giao hàng từ hòn đảo $U_i$ đến hòn đảo $V_i$ theo đường đi ghé qua ít hòn đảo nhất. Tuấn chỉ có thể thực hiện nhiệm vụ giao hàng thứ $i$ nếu vị trí của Tuấn đang ở $U_i$ và sau khi hoàn thành giao hàng thì vị trí của Tuấn sẽ là $V_i$. Lưu ý đối với mỗi nhiệm vụ, Tuấn có thể thực hiện hoặc từ chối giao hàng. Đối với mỗi hòn đảo, công ty sẽ đặt một giá trị phần thưởng mà người giao hàng có thể nhận được cho mỗi lần ghé qua. Với mỗi nhiệm vụ hoàn thành, Tuấn sẽ nhận được phần thưởng là giá trị lớn nhất trong số các giá trị của các hòn đảo nằm trên đường đi giao hàng, tính cả hòn đảo xuất phát và hòn đảo kết thúc.

Yêu cầu: Hãy tính tổng giá trị phần thưởng lớn nhất mà Tuấn có thể nhận được sau $K$ nhiệm vụ.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $N$ là số lượng hòn đảo ($1\le N\le 2\times {10}^5$).
• Dòng thứ hai chứa $N$ số nguyên $W_1,W_2,\dots ,W_N$ là giá trị phần thưởng tại các hòn đảo ($0\le W_1,W_2,\dots ,W_N\le {10}^9$).
• Mỗi dòng trong số $N-1$ dòng tiếp theo chứa 2 số nguyên dương thể hiện cây cầu kết nối giữa 2 hòn đảo.
• Dòng tiếp theo chứa một số nguyên $K$ là số lượng nhiệm vụ ($1\le K\le 2\times {10}^5$).
• Dòng thứ $i$ trong số $K$ dòng tiếp theo chứa 2 số nguyên $U_i$ và $V_i$ thể hiện nhiệm vụ giao hàng thứ $i$ ($1\le U_i,V_i\le N$; $U_i\ne V_i$).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất thể hiện tổng giá trị phần thưởng lớn nhất mà Tuấn có thể nhận được sau $K$ nhiệm vụ.

Ràng buộc

• $1\le N\le 2\times {10}^5$; $1\le K\le 2\times {10}^5$.
• $0\le W_i\le {10}^9$.
• $1\le U_i,V_i\le N$; $U_i\ne V_i$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N,K\le 100$ và hòn đảo $i$ có cây cầu nối với hòn đảo $i+1$ ($\forall i:1\le i\le N-1$).
• Subtask 2 ($20\%$ số điểm): $N\le 10000$, $K\le 100$ và hòn đảo $i$ có cây cầu nối với hòn đảo $i+1$ ($\forall i:1\le i\le N-1$).
• Subtask 3 ($20\%$ số điểm): hòn đảo $i$ có cây cầu nối với hòn đảo $i+1$ ($\forall i:1\le i\le N-1$).
• Subtask 4 ($20\%$ số điểm): $N\le 10000$ và $K\le 100$.
• Subtask 5 ($20\%$ số điểm): không có ràng buộc nào thêm.

Ví dụ