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:

• there must exist a simple path of ~K~ ornaments that consists of alternating coloured ornaments

What is the minimum cost to turn the tree valid? It is guaranteed there will exist a solution.

Input Specification

The first line contains the spaced integers ~N~ and ~K~ ~(1 \le N,K \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
3 1 3 3 2
GGRRR
1 2
1 3
2 4
2 5

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

By swapping ornaments ~2~ and ~5~, there exists a path of length ~4~ of colour-alternating ornaments (~3 \rightarrow 1 \rightarrow 2 \rightarrow 5~). The total cost is ~1 + 2 = 3~.

Sample Input 2

11 5
4 3 3 2 3 4 2 3 2 1 2
RRRRRRRRRRR
1 2
1 3
2 4
2 5
4 6
3 7
3 8
7 9
7 10
8 11

Output for Sample Input 2

5

Explanation of Output for Sample Input 2

By swapping ornaments ~7~ and ~8~, the colour-alternating path of ~10 \rightarrow 7 \rightarrow 3 \rightarrow 8 \rightarrow 11~ makes the tree valid for a minimal cost of ~2 + 3 = 5~.

Sample Input 3

16 6
1 4 3 3 3 2 2 4 3 3 2 2 1 3 1 4
RGRRGGGRRRRRGRRG
1 2
1 3
1 4
2 5
2 6
2 7
3 8
8 9
8 10
3 11
3 12
11 13
7 14
7 15
4 16

Output for Sample Input 3

4

Explanation of Output for Sample Input 3

By swapping ornaments ~1~, ~11~, and ~13~, the colour-alternating path of ~16 \rightarrow 4 \rightarrow 1 \rightarrow 3 \rightarrow 11 \rightarrow 13~ makes the tree valid for a minimal cost of ~1 + 2 + 1 = 4~.