問題文

N 個の頂点と M 本の辺からなるグラフが与えられます。
i 番目の辺は A_i と B_i を双方向に結んでいます。
そして、各頂点には G,C,P のいずれかの文字が書かれています。
さて、anmichiくんとdefineくんは次のようなじゃんけんゲームをします。

• 自分が G と書かれた頂点にいるかつ相手が C と書かれた頂点にいる
• 自分が C と書かれた頂点にいるかつ相手が P と書かれた頂点にいる
• 自分が P と書かれた頂点にいるかつ相手が G と書かれた頂点にいる

• 自分が C と書かれた頂点にいるかつ相手が G と書かれた頂点にいる
• 自分が P と書かれた頂点にいるかつ相手が C と書かれた頂点にいる
• 自分が G と書かれた頂点にいるかつ相手が P と書かれた頂点にいる

• 自分のいるマスに書かれた文字と相手のいるマスに書かれた文字が同じ

初め、anmichiくんは頂点 1 に、defineくんは頂点 N にいます。
また、初めの両者の得点は 0 点です。
二人は次のような動作を K 回行います。

1. 辺で隣接する頂点に移動する、もしくは今いる頂点から移動しない。二人が同じ頂点に移動することもできる。
2. じゃんけんに勝ったら X 点、あいこなら Y 点、負けたら 0 点が加算される。

また、defineくんはどのように動くかを事前に決めており、 i (1 \leq i \leq K) 手目には頂点 D_i に移動します。
なお、anmichiくんはdefineくんがどのように動くかを知っています。
さて、anmichiくんは自分のスコアを最大化するように動くとき、何点もらえるか出力してください。
ただし、二人はどのマスに何の文字が書かれているか知っているものとします。

制約

• 入力で与えられる数は全て整数である。
• 2 \leq N \leq 2000
• 1 \leq M \leq 5000
• 1 \leq K \leq 2000
• 1 \leq Y < X \leq 100
• 1 \leq A_i,B_i \leq N
• C_i は G, C, P のいずれかである。
• 1 \leq D_i \leq N
• N = D_1 であるか、頂点 N と頂点D_1を結ぶ辺は存在する。
• 1 \leq i \leq K-1 を満たす全ての i について、D_i = D_{i+1} であるか、頂点 D_i と頂点 D_{i+1} を結ぶ辺は存在する。
• 入力で与えられるグラフは単純であるが、連結であるとは限らない。

入力例1

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

出力例1

6

入力例2

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

出力例2

9