#P1013. 小夜丸的连夜出逃
小夜丸的连夜出逃
Problem Description
小夜丸站在自己地下迷宫的起点,她现在被追捕,要带上自己尽可能多的财宝跑路。
她的地下迷宫由n个点构成,每个点内有一定数量的财宝以及m个的单向传送门,每个可以把她传送到对应的点。
在某些点中有红色的逃脱按钮,她如果要逃脱必须要得到至少一个按钮。
小夜丸不知道到底最多能带走多少财宝于是就去求问OZDimensional,OZDimensional也不是很清楚于是求助与你,
起点为1。
请你求出小夜丸最多可以带走多少财宝离开,如果逃不走就输出-1。
Input Format
第一行输入三个整数,表示有个点,个传送门,个点放有逃脱按钮。
接下来行,每一行输入两个整数,表示有一个在点有一个通向点的单向传送门。
接下来行,每一行输入一个整数,按顺序表示在点有价值为w的财宝。例如在第一行就表示在第一个点中有价值为的财宝。
接下来行,每一行输入一个整数,表示点放有逃脱按钮。
保证传送门没有重复的并且。
Output Format
一行一个整数表示最大可以得到的价值总和,如果无法逃脱,输出-1。
Sample
输入
6 5 1
1 2
2 3
5 3
4 5
1 4
2
1
10
3
4
5
2
输出
13
Hint
$1 \le n \le 10^{5}, 1 \le m \le 3*10^{5}, 1 \le u,v,s,p \le n,1 \le w \le 5000$
相关
在下列比赛中: