← 返回题目列表

AtCoder · tkppc4_1_l

L. 石头、剪刀、布

中文机器翻译题面 查看原题

配点 : 500 点

問題文

N 顶点和 M 给您一张由书本边缘组成的图表。
i 第边是 它是朝向 A_i 和 按字典顺序比较 B_i 进行双向连接。
对于每个顶点 G,C,P 。
现在,anmichi-kun和define-kun将玩下面的石头剪刀布游戏。

[石头剪刀布规则]

(☆)如果你赢了
  • 我自己 G 在顶部,对手是 我在顶部标记为 C 我在上面写着的地方
  • 我自己 C 在顶部,对手是 我在顶部标记为 P 我在上面写着的地方
  • 我自己 P 在顶部,对手是 我在顶部标记为 G 我在上面写着的地方
(★) 如果你输了
  • 我自己 C 在顶部,对手是 我在顶部标记为 G 我在上面写着的地方
  • 我自己 P 在顶部,对手是 我在顶部标记为 C 我在上面写着的地方
  • 我自己 G 在顶部,对手是 我在顶部标记为 P 我在上面写着的地方
(△)说到爱情
  • 你所在方格上写的字符与对手所在方格上写的字符相同。

起初,anmichi 处于顶部。 1 ,define-kun 在顶部 N 。 假设
另外,两者的初始分数均为 0 点。
两者执行以下操作。 K 次。 指定

  1. 移动到边上的相邻顶点,或者从当前顶点不移动。两个人也可以移动到同一个顶点。
  2. 如果你赢了石头剪刀布 X 点,爱子 Y 积分,如果你输了 0 积分已添加。

另外,define君预先决定如何移动。 i (1 \leq i \leq K) 手上的顶点 D_i 。
而且,安道君知道define君的动作。
现在,当安道君移动以最大化他的分数时,请输出他得到了多少分。
然而,假设两个人都知道哪个字母写在哪个方格上。

制約

  • 输入中给出的所有数字均为整数。
  • 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} 。
  • 作为输入给出的图很简单,但不一定是连通的。

入力

输入是按以下格式从标准输入给出的。

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

出力

安道君的最高分 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 移动。请注意,也可以不移动。

作者: 安道 作为