TopCoder

User's AC Ratio

90.5% (38/42)

Submission's AC Ratio

37.3% (66/177)

Tags

Description

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

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

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

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

Input Format

第一行包含兩個整數 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 的單向的道路到達其中的至少一個酒吧。

Output Format

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

Sample Input 1

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

Sample Output 1

47

Hints

Problem Source

原TIOJ1744 / APIO '09

Subtasks

No. Testdata Range Score
1 0 6
2 1 6
3 2 6
4 3 6
5 4 6
6 5 6
7 6 6
8 7 6
9 8 6
10 9 6
11 10 6
12 11 6
13 12 6
14 13 6
15 14 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 2
2 1000 131072 262144 3
3 1000 131072 262144 4
4 1000 131072 262144 5
5 1000 131072 262144 6
6 1000 131072 262144 7
7 1000 131072 262144 8
8 1000 131072 262144 9
9 1000 131072 262144 10
10 1000 131072 262144 11
11 1000 131072 262144 12
12 1000 131072 262144 13
13 1000 131072 262144 14
14 1000 131072 262144 15