Ở 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. Bạn đầ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 \leq i \leq 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ụ.

Input

Vào từ file văn bản SHIP.INP:

• Dòng đầu chứa một số nguyên ~N~ là số lượng hòn đảo (~1 \leq N \leq 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 \leq W_1, W_2, \dots, W_N \leq 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 \leq K \leq 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 \leq U_i, V_i \leq N; U_i \neq V_i~).

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

Output

Ghi ra file văn bản SHIP.OUT:

• 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ụ.

Scoring

Sample Input 1

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

Sample Output 1

6

Sample Input 2

7
1 5 5 7 3 16 1
1 4
1 2
2 3
4 5
5 6
5 7
7
1 3
3 2
1 4
4 2
2 5
5 7
5 6

Sample Output 2

37