AT_ttpc2022_j.Jewel Game

给定一个有 $N$ 个顶点、$M$ 条边的有向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边（$1 \leq i \leq M$）是从顶点 $A_i$ 指向顶点 $B_i$。这个图中可能包含自环，但不存在重边。保证每个顶点至少有一条从该顶点出发的边。

在 $N$ 个顶点中，有 $K$ 个顶点上放置了宝石。第 $i$ 个（$1 \leq i \leq K$）宝石放在顶点 $V_i$ 上，价值为 $W_i$。

First 君和 Second 君在这个图上进行游戏。游戏开始时，First 君在顶点 $F$，Second 君在顶点 $S$。First 君先手，之后两人轮流进行以下操作：

• 从自身当前位置出发，选择一条外连的边，沿该边移动到下一个顶点。如果到达的顶点上有宝石，就获得该宝石，并将它从图上移除。

当所有宝石被取走，或游戏过程中出现与之前完全相同的局面（即轮到谁行动、两位玩家的位置、剩余宝石的分布三者都与之前任一回合一致），游戏便结束。

两人都以最大化“自己获得的宝石总价值 $-$ 对方获得的宝石总价值”为目标行动。请计算当两人都采取最优策略时，游戏结束时 First 君获得的宝石总价值 $-$ Second 君获得的宝石总价值。

输入以如下格式从标准输入读入：

N M F S
A_1 B_1
⋮
A_M B_M
K
V_1 W_1
⋮
V_K W_K

输出一行答案。

样例解释 1

任意顶点都可到达所有宝石。游戏流程如下：

• First 君从顶点 $1$ 移动到顶点 $5$，获得价值 $96$ 的宝石。
• Second 君从顶点 $1$ 移动到顶点 $3$，获得价值 $84$ 的宝石。
• First 君从顶点 $5$ 移动到顶点 $4$，获得价值 $38$ 的宝石。
• Second 君从顶点 $3$ 移动到顶点 $2$，获得价值 $4$ 的宝石。

于是答案为 $(96 + 38) - (84 + 4) = 46$。

数据范围

• 输入均为整数。
• $2 \leq N \leq 30$
• $1 \leq F, S \leq N$
• $1 \leq A_i, B_i \leq N$（$1 \leq i \leq M$）
• $(A_i, B_i) \neq (A_j, B_j)$（$1 \leq i < j \leq M$）
• 对任意 $x$（$1 \leq x \leq N$），存在 $A_i = x$ 的 $i$。
• $1 \leq K \leq 10$
• $1 \leq V_1 < \dots < V_K \leq N$
• $V_i \notin \{F, S\}$（$1 \leq i \leq K$）
• $1 \leq W_i \leq 10^8$（$1 \leq i \leq K$）

由 ChatGPT 5 翻译