AT_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$ 分，失败不得分。 define 君已经事先计划好第 $i\ (1 \leq i \leq K)$ 轮要去的顶点，也就是 $D_i$。anmichi 君了解对方的移动计划，目的是最大化自己的得分。请计算 anmichi 君在最佳策略下能获得的最高分。假设两人都知道每个顶点上标记的字符。

输入数据如下： > $N$ $M$ $K$ $X$ $Y$ $A_1$ $B_1$ $A_2$ $B_2$ $\ldots$ $A_M$ $B_M$ $C_1$ $C_2$ $\ldots$ $C_N$ > $D_1$ $D_2$ $\ldots$ $D_K$

输出 anmichi 君可以获得的最大得分。 ## 数据范围 - 每个输入都是整数。 - $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$，$D_i = D_{i+1}$ 或者顶点 $D_i$ 与顶点 $D_{i+1}$ 之间连通。 - 图是简单图，不一定连通。 **本翻译由 AI 自动生成**

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