【模板】缩点

题目背景

缩点+DP

题目描述

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

输入输出格式

输入格式


第一行,n,m 第二行,n个整数,依次代表点权 第三至m+2行,每行两个整数u,v,表示u->v有一条有向边

输出格式


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

输入输出样例

输入样例 #1

2 2
1 1
1 2
2 1

输出样例 #1

2

说明

n<=10^4,m<=10^5,0<=点权<=1000 算法:Tarjan缩点+DAGdp