1518：抢掠计划

题目描述

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆祝他的胜利。

使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机里面就不会再有钱了。

输入格式

第一行包含两个整数 $N, M$。$N$ 表示路口的个数，$M$ 表示道路条数。

接下来 $M$ 行，每行两个整数，这两个整数都在 $1$ 到 $N$ 之间，第 $i+1$ 行的两个整数表示第 $i$ 条道路的起点和终点的路口编号。

接下来 $N$ 行，每行一个整数，按顺序表示每个路口处的 ATM 机中的钱数 $money_i$。

接下来一行包含两个整数 $S, P$，$S$ 表示市中心的编号，也就是出发的路口。$P$ 表示酒吧数目。

接下来的一行中有 $P$ 个整数，表示 $P$ 个有酒吧的路口的编号。

输出格式

输出一个整数，表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

样例

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

样例输出 #1

47

样例解释 #1

• $N=6$ 个路口，$M=7$ 条单向道路。
• 道路：
  1. $1 \to 2$
  2. $2 \to 3$
  3. $3 \to 5$
  4. $2 \to 4$
  5. $4 \to 1$
  6. $2 \to 6$
  7. $6 \to 5$
• 每个路口的 ATM 钱数：
  • 路口 $1$：$10$
  • 路口 $2$：$12$
  • 路口 $3$：$8$
  • 路口 $4$：$16$
  • 路口 $5$：$1$
  • 路口 $6$：$5$
• 出发路口 $S=1$，酒吧数目 $P=4$，酒吧所在路口为 $4,3,5,6$。
• Banditji 可以重复经过路口，但每个路口的 ATM 只能抢一次。
• 最优路线：$1 \to 2 \to 4 \to 1 \to 2 \to 3 \to 5$
  • 经过的路口：$1$（抢 $10$），$2$（抢 $12$），$4$（抢 $16$），回到 $1$（已抢过，不再有钱），再到 $2$（已抢过），再到 $3$（抢 $8$），再到 $5$（抢 $1$）。
  • 总金额：$10+12+16+8+1 = 47$。
• 注意：他最终停在酒吧路口 $5$（因为 $5$ 是酒吧之一）。

数据范围

• 对于 $50\%$ 的数据，$N, M \le 3000$。
• 对于 $100\%$ 的数据，$N, M \le 500000$。
• 每个 ATM 机中可取的钱数为一个非负整数且不超过 $4000$。
• 输入数据保证你可以从市中心沿着 Siruseri 的单向的道路到达其中的至少一个酒吧。

时空限制

• 时间限制：1000 ms
• 内存限制：131072 KB

注意：本题需要先进行强连通分量缩点（因为可以重复经过，所以一个强连通分量内的所有 ATM 都可以被抢到），每个强连通分量的总金额为分量内所有路口 ATM 钱数之和。缩点后得到 DAG，然后从起点 $S$ 所在的强连通分量出发，求到任意一个酒吧所在强连通分量的最长路径（最大点权和）。由于 DAG 上最长路径可以通过拓扑排序 + DP 求解。注意起点可能无法到达某些酒吧，只计算可达的酒吧。最终答案是所有酒吧所在强连通分量中，从起点出发能到达的且距离（累计金额）最大的那个值。