Problem : 235 - ATM

Problem Statistics

Solved Member: 25　　Submission: 130　　User Tried: 26

Statement:

Siruseri 城中的道路都是單向的。不同的道路由路口連接。
按照法律的規定，在每個路口都設立了一個 Siruseri 銀行的 ATM 取款機。
令人奇怪的是，Siruseri的酒吧也都設在路口，雖然並不是每個路口都設有酒吧。

Banditji 計畫實施 Siruseri 有史以來最驚天動地的 ATM 搶劫。
他將從市中心出發，沿著單向道路行駛，搶劫所有他途徑的 ATM 機，最終他將在一個酒吧慶祝他的勝利。

使用高超的駭客技術，他獲知了每個 ATM 機中可以掠取的現金數額。
他希望你幫助他計算從市中心出發最後到達某個酒吧時最多能搶劫的現金總數。
他可以經過同一路口或道路任意多次。
但只要他搶劫過某個 ATM 機後，該 ATM 機裏面就不會再有錢了。
例如，假設該城中有 6 個路口，道路的連接情況如下圖所示：

市中心在路口 1，由一個入口符號→來標識，那些有酒吧的路口用雙圈來表示。
每個 ATM 機中可取的錢數標在了路口的上方。
在這個例子中，Banditji 能搶劫的現金總數為 47，實施的搶劫路線是：1-2-4-1-2-3-5。

Input:Output:

第一行包含兩個整數 N、M。N 表示路口的個數，M 表示道路條數。
接下來M 行，每行兩個整數，這兩個整數都在 1 到 N 之間，
第 i+1 行的兩個整數表示第i 條道路的起點和終點的路口編號。
接下來 N 行，每行一個整數，按順序表示每個路口處的 ATM 機中的錢數。
接下來一行包含兩個整數 S、P，S 表示市中心的編號，也就是出發的路口。P 表示酒吧數目。
接下來的一行中有 P 個整數，表示P 個有酒吧的路口的編號。

50%的輸入保證 N, M≤3000。所有的輸入保證 N, M≤500000。
每個 ATM機中可取的錢數為一個非負整數且不超過 4000。
輸入資料保證你可以從市中心沿著 Siruseri 的單向的道路到達其中的至少一個酒吧。

輸出一個整數，表示 Banditji 從市中心開始到某個酒吧結束所能搶劫的最多的現金總數。

Sample Input:Sample Output:

6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1
5
1 4
4 3 5 6

Source:

APIO 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	3000ms	65536kb
1	3000ms	65536kb	4
2	3000ms	65536kb	3
3	3000ms	65536kb	3
4	3000ms	65536kb	10
5	3000ms	65536kb	10
6	3000ms	65536kb	5
7	3000ms	65536kb	5
8	3000ms	65536kb	5
9	3000ms	65536kb	5
10	3000ms	65536kb	13
11	3000ms	65536kb	13
12	3000ms	65536kb	7
13	3000ms	65536kb	7
14	3000ms	65536kb	5
15	3000ms	65536kb	5