【模板】缩点

题目描述

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个整数，依次代表点权。

第三行至第 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。

输出格式

共一行，一个整数，表示答案。

输入输出样例 #1

输入 #1

2 2
1 1
1 2
2 1

输出 #1

2

输入输出样例 #2

输入 #2

10 10
10 20 30 40 50 60 70 80 90 100
1 2
2 3
3 1
4 5
5 6
6 4
1 4
4 7
7 8
8 9

输出 #2

450

说明/提示

对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m\le 10^5$，$0\le$ 点权 $\le 10^3$。