AndyMan68 has a wonderful Christmas tree! His Christmas tree has ~N~ ornaments, where ~N-1~ branches connect the ornaments together on the tree, such that there is exactly one path of branches from any ornament to any other ornament. The ornaments are numbered from ~1~ to ~N~, where the ~i^{\text{th}}~ ornament is either green or red, and has a cost ~c_i~ to swap its colour.

AndyMan68 would like to swap some of the ornaments to make his tree valid. A tree is considered valid if:

• for every pair of red ornaments ~u~ and ~v~, the path on the tree from ornament ~u~ to ~v~ must consist of all red ornaments

What is the minimum cost to turn the tree valid?

Input Specification

The first line contains the integer ~N~ ~(1 \le N \le 10^5)~, the number of ornaments on the tree.

The next line contains ~N~ spaced integers ~c_1, c_2, ... c_N~, where the cost of swapping the colour of the ~i^{\text{th}}~ ornament is ~c_i~ ~(1 \le c_i \le 10^5)~.

The next line contains a string of length ~N~, where the ~i^{\text{th}}~ character is either G to indicate that the ~i^{\text{th}}~ ornament is green, or R to indicate that it's red.

The next ~N-1~ lines contains ~2~ spaced integers ~u_i~ and ~v_i~, denoting a branch connecting the ornaments ~u_i~ and ~v_i~ ~(1 \le u_i, v_i \le N)~.

Output Specification

On a single line, output the minimal cost to turn the tree valid.

Sample Input 1

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

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

A suboptimal way to make the tree valid is to swap ornaments ~1~ and ~2~ for a total cost of ~4 + 2 = 6~.

Swapping ornaments ~3~ and ~5~ for a total cost of ~1 + 3 = 4~ is better, but not the most optimal. Notice that even with just a singular red ornament, it meets the conditions of being a valid tree as there is no pair of red ornaments that violates the requirement of being a valid tree.

However, the most optimal is to swap ornaments ~2~ and ~3~ for a total cost of ~2 + 1 = 3~.

Sample Input 2

8
3 1 4 2 1 2 2 1
RGGGRRRR
1 2
1 3
2 4
4 5
2 6
3 7
3 8

Output for Sample Input 2

5

Explanation of Output for Sample Input 2

By swapping nodes ~2~, ~5~, ~7~, and ~8~, the tree can be made valid for a minimal total cost of ~1 + 1 + 2 + 1 = 5~.