L - じゃんけん /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

N 個の頂点と M 本の辺からなるグラフが与えられます。
i 番目の辺は A_iB_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_iG, 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} を結ぶ辺は存在する。
  • 入力で与えられるグラフは単純であるが、連結であるとは限らない。

入力

入力は以下の形式で標準入力から与えられます。

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

出力

anmichiくんのスコアの最大値を 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

頂点 1 -> 3 -> 1 と動くと 2 回勝つことができ、3 \times 2 = 6 点を得ることができます。
7 点以上を得る方法は存在しません。


入力例2

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

出力例2

9

頂点 1 から動かないのが最適となります。動かないことも可能なことに注意してください。

writer: anmichi