给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $M$。第 $i$（$1 \le i \le M$）条边从顶点 $U_i$ 指向顶点 $V_i$。图中可能包含自环，但没有重边。保证每个顶点至少有一条出边。

有 $K$ 颗宝石放置在某些顶点上。第 $i$（$1 \le i \le K$）颗宝石位于顶点 $X_i$，价值为 $W_i$。

Alice 和 Bob 正在利用这个图玩一个游戏。游戏开始时，Alice 位于顶点 $A$，Bob 位于顶点 $B$。由 Alice 开始，Alice 和 Bob 轮流执行以下操作：

• 选择一条从当前所在顶点出发的出边，并沿着该边移动到下一个顶点。如果下一个顶点有宝石，他们会拿走该宝石并将其从图中移除。

当所有宝石都被拿走，或者当前的游戏状态（轮次、两名玩家的位置、剩余的宝石）在之前出现过时，游戏结束。在游戏结束时，游戏的得分定义为：

(Alice 拿走的宝石价值总和) $-$ (Bob 拿走的宝石价值总和)

Alice 希望最大化这个得分，而 Bob 希望最小化这个得分。求当两名玩家都采取最优策略时游戏的得分。

输入格式

输入通过标准输入给出，格式如下：

N M A B
U_1 V_1
:
U_M V_M
K
X_1 W_1
:
X_K W_K

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 30$
• $1 \le A, B \le N$
• $1 \le U_i, V_i \le N$ ($1 \le i \le M$)
• $(U_i, V_i) \neq (U_j, V_j)$ ($1 \le i < j \le M$)
• 对于每个 $x$ ($1 \le x \le N$)，至少存在一个 $i$ 使得 $U_i = x$。
• $1 \le K \le 10$
• $1 \le X_1 < \dots < X_K \le N$
• $X_i \notin \{A, B\}$ ($1 \le i \le K$)
• $1 \le W_i \le 10^8$ ($1 \le i \le 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

输入样例 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