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 翻译