You are currently living on in a colony on mars. The environment outside is impossible to live in, so the colony is organised as ~n~ habitats connected by ~n-1~ tunnels, (forming a tree). Each of these habitats has a garden which each produce some amount of oxygen.

However, a meteor storm has caused damage to ~m~ habitats, causing them to leak oxygen. You decide to seal off some of the tunnels, and continue to live in some connected section of the colony.

After sealing off the tunnels, what is the maximum oxygen production of the remaining section of the colony.

Input

The first line contains two integers, ~n~ and ~m~.

The second line contains integers ~a_1, \dots, a_n~, denoting that the ~i~-th habitat produces ~a_i~ units of oxygen.

The following ~n-1~ lines contain integers ~u, v~, denoting that a tunnel exists between habitat ~u~ and habitat ~v~.

Finally, the following ~m~ lines contains integers ~u, l~, denoting that habitat ~u~ is leaking ~l~ units of oxygen.

Output

Output an integer, which is the maximum oxygen production of the remaining section of the colony, after sealing off some tunnels.

Constraints

• ~1 \le m,u,v \le n \le 10^5~
• ~1 \le a_i, l \le 10^9~

Example 1

Input

10 5
10 1 10 7 7 3 6 10 1 6 
1 2
1 3
1 4
2 5
2 6
1 7
7 8
8 9
9 10
6 18
10 15
7 6
3 18
3 13

Output

36

Example 2

Input

10 7
4 8 10 6 9 5 4 5 5 4 
1 2
1 3
3 4
3 5
2 6
6 7
6 8
3 9
8 10
6 16
7 9
2 20
4 10
8 8
6 5
7 13

28