Problem Description

You are given a graph consisting of $ N $ vertices and $ M $ edges.
The $ i $ -th edge connects vertices $ A_i $ and $ B_i $ bidirectionally.
Each vertex is labeled with one of the characters G, C, or P.
Anmichi and Define will play a rock-paper-scissors game according to the following rules:

【Rock-Paper-Scissors Rules】

(☆) Winning conditions - You are on a vertex labeled G and your opponent is on a vertex labeled C
- You are on a vertex labeled C and your opponent is on a vertex labeled P
- You are on a vertex labeled P and your opponent is on a vertex labeled G

(★) Losing conditions - You are on a vertex labeled C and your opponent is on a vertex labeled G
- You are on a vertex labeled P and your opponent is on a vertex labeled C
- You are on a vertex labeled G and your opponent is on a vertex labeled P

(△) Draw conditions - The characters written on the vertices where you and your opponent are located are the same

Initially, Anmichi is at vertex $ 1 $ and Define is at vertex $ N $.
Both start with a score of $ 0 $.
They will perform the following actions $ K $ times:

1. Move to an adjacent vertex or stay at the current vertex. Both can move to the same vertex.
2. If you win the rock-paper-scissors, you get $ X $ points; if it's a draw, you get $ Y $ points; if you lose, you get $ 0 $ points.

Define has predetermined his moves, and on the $ i $ -th move ( $1 \leq i \leq K$ ), he will move to vertex $ D_i $.
Anmichi knows Define's moves in advance.
Anmichi will move to maximize his score. Output the maximum score Anmichi can achieve.
Assume both know what characters are written on which vertices.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ X $ $ Y $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $\vdots$ $ A_M $ $ B_M $ $ C_1 $ $ C_2 $ $\ldots$ $ C_N $
$ D_1 $ $ D_2 $ $\ldots$ $ D_K $

Output Format

Output the maximum score Anmichi can achieve in one line.

Sample Input and Output

Sample Input #1

4 5 2 3 21 21 31 42 43 4G C P P1 2

Sample Output #1

6

Sample Input #2

5 4 3 5 3
1 2
2 3
3 4
4 5
G C C G G
4 5 4

Sample Output #2

9

Notes/Hints

Constraints

• All numbers given in the input are integers.
• $2 \leq N \leq 2000$
• $1 \leq M \leq 5000$
• $1 \leq K \leq 2000$
• $1 \leq Y$
• $1 \leq A_i, B_i \leq N$
• $ C_i $ is one of G, C, P.
• $1 \leq D_i \leq N$
• Either $ N = D_1 $ or there is an edge connecting vertex $ N $ and vertex $ D_1 $.
• For all $ i $ satisfying $1 \leq i \leq K-1$, either $ D_i = D_{i+1} $ or there is an edge connecting vertex $ D_i $ and vertex $ D_{i+1} $.
• The graph given in the input is simple but not necessarily connected.

见题面 Input 部分

见题面 Output 部分