配点 : 400 点
問題文
N 頂点 M 给定了一个有向边的图。顶点标有 1 减去 N 号码位于侧面。
它的编号为 1 减去 M 的编号,边是指向 i (1 ≤ i ≤ M) 是顶点 A_i 到顶点 B_i 的边。该图可能存在自环,但没有重边。保证从任何顶点出发的边数至少为 1 条。
个顶点中有 K 个放置了宝石。i 番目 (1 ≤ i ≤ K号宝石位于顶点 V_i ,价值为 W_i 。
。使用这个图,First 君和 Second 君进行游戏。游戏开始时,First 君在顶点 F ,Second 君在顶点 S 。从 First 君开始,First 君和 Second 君交替执行以下操作:
- 从自己当前所在的顶点出发的边 1 选择一条边,沿着它移动到下一个顶点。如果移动到的顶点上有宝石,就将其收集,同时该宝石将从图上移除。
当收集完所有宝石,或游戏中出现了与之前盘面完全相同的情况(轮次、每个玩家的位置、剩余宝石状态完全相同)时,游戏结束。
双方都将尽量行动,使(自己收集的宝石价值总和) - (对方收集的宝石价值总和)尽可能大,因此在游戏结束时求(First君收集宝石的价值总和) - (Second君收集宝石的价值总和)。
制約
- 所有输入均为整数
- 2 ≤ N ≤ 30
- 1 ≤ F, S ≤ N
- 1 ≤ A_i, B_i ≤ N (1 ≤ i ≤ M)
- (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)
- 哪个 x (1 \le x \le N)也适用。 A_i = x 纳鲁 如果 i 存在
- 1 ≤ K ≤ 10
- 1 ≤ V_1 < \dots < V_K ≤ N
- V_i \notin \{F, S\} (1 ≤ i ≤ K)
- 1 ≤ W_i ≤ 10^8 (1 ≤ i ≤ K)
入力
输入是按以下格式从标准输入给出的。
N M F S A_1 B_1 \vdots A_M B_M K V_1 W_1 \vdots V_K W_K
出力
打印答案。 来自
入力例 1
5 16 1 1 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 2 3 4 3 5 4 2 4 3 4 5 5 2 5 3 5 4 4 2 4 3 84 4 38 5 96
出力例 1
46
可以从任意顶点收集任何宝石。游戏按以下方式进行:
- First君移动到顶点 1 到顶点 5 并获得价值为 96 的宝石。
- Second君移动到顶点 1 到顶点 3 并获得价值为 84 的宝石。
- First君移动到顶点 5 到顶点 4 并获得价值为 38 的宝石。
- Second君移动到顶点 3 到顶点 2 并获得价值为 4 的宝石。
因此,答案是 (96 + 38) - (84 + 4) = 46 。
入力例 2
8 16 8 4 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 1 5 2 6 3 7 4 8 5 1 6 2 7 3 8 4 6 1 29 2 34 3 41 5 7 6 26 7 94
出力例 2
-23
入力例 3
5 5 2 1 1 1 2 3 3 4 4 5 5 2 2 4 1000000 5 100000
出力例 3
1100000
入力例 4
10 20 1 2 1 4 1 7 2 2 2 4 3 6 3 3 4 8 4 7 5 7 5 1 6 9 6 2 7 9 7 3 8 8 8 6 9 7 9 8 10 10 10 2 8 3 92067840 4 2874502 5 36253165 6 70758738 7 4768969 8 16029185 9 16207515 10 44912151
出力例 4
132484345