AT_tkppc4_1_l じゃんけん

[problemUrl]: https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l $ 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くんは自分のスコアを最大化するように動くとき、何点もらえるか出力してください。 ただし、二人はどのマスに何の文字が書かれているか知っているものとします。

入力は以下の形式で標準入力から与えられます。 > $ 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 $ 行に出力してください。

### 制約 - 入力で与えられる数は全て整数である。 - $ 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 $ は `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} $ を結ぶ辺は存在する。 - 入力で与えられるグラフは単純であるが、連結であるとは限らない。