【模板】缩点

题目背景

缩点+DP

题目描述

给定一个 $n$ 个点 $m$ 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

输入输出格式

输入格式


第一行两个正整数 $n,m$ 第二行 $n$ 个整数,依次代表点权 第三至 $m+2$ 行,每行两个整数 $u,v$,表示一条 $u\rightarrow v$ 的有向边。

输出格式


共一行,最大的点权之和。

输入输出样例

输入样例 #1

2 2
1 1
1 2
2 1

输出样例 #1

2

说明

【数据范围】 对于 $100\%$ 的数据,$1\le n \le 10^4$,$1\le m \le 10^5$,点权 $\in [0,1000]$ 算法:Tarjan 缩点 + DAGdp