問題文

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)

入力例 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