题目描述

Mr. Dog 被公司解雇了。为了养活家人，他必须尽快找到一份新工作。如今，由于失业人数不断增加，找工作并不容易，因此一些公司经常采用很难的测试来招聘员工。

测试是这样的：你从一座起点城市出发，可以经过一些有向道路到达另一座城市。每到达一座城市，你都可能获得一些收益，也可能需要支付一些费用。这个过程持续到你到达一座终点城市。老板会计算你在旅途中花费的费用以及刚刚获得的收益，最后决定是否录用你。

为了得到这份工作，Mr. Dog 设法获知了他可能到达的所有城市的净收益 $V_i$（$V_i$ 为负数表示花钱而不是赚钱），以及各城市之间的连接关系。没有任何道路通向它的城市称为起点城市；没有道路从它通向其他城市的城市称为终点城市。

Mr. Dog 的任务是从任意一座起点城市出发，选择一条通往某座终点城市的路线，使他能够获得的总收益最大。

输入格式

输入文件包含若干组测试数据，读到文件结束为止。

每组测试数据的第一行包含两个整数 $n,m$，分别表示城市数量和道路数量。

接下来的 $n$ 行中，每行包含一个整数。第 $i$ 行给出城市 $i$ 的净收益 $V_i$，满足 $0\le |V_i|\le 20000$。

接下来的 $m$ 行中，每行包含两个整数 $x,y$，表示有一条从城市 $x$ 通向城市 $y$ 的有向道路。

保证每条道路在输入中恰好出现一次，并且不存在能够回到先前城市的路线，也就是说整张图是有向无环图。

输出格式

对于每组测试数据输出一行，其中包含一个整数，表示 Mr. Dog 能够获得的最大总收益；如果所有可行路线都会产生支出，则这个整数表示他必须承担的最小支出所对应的净收益。

输入样例 #1

6 5
1
2
2
3
3
4
1 2
1 3
2 4
3 4
5 6

输出样例 #1

7

输入样例 #2

9 36
-1361 8884 -841 2452 -419 6168 -7606 -7757 5213
3 4
4 9
3 7
4 6
5 7
8 9
1 6
2 5
1 3
1 9
2 8
6 8
4 5
3 9
5 6
4 8
3 6
5 9
2 4
1 2
2 7
1 5
1 8
7 9
6 7
4 7
3 5
3 8
5 8
1 4
2 3
2 9
1 7
2 6
6 9
7 8

输出样例 #2

21356

输入样例 #3

15 75
-9601 -4517 -2825 -1366 -5723 -702 -2343 2407 -1484 7630 9186 592 6491 6201 -913
6 12
3 4
4 6
4 12
3 10
12 13
5 7
5 10
8 9
9 14
9 11
2 5
2 11
1 9
10 12
2 8
2 14
13 14
1 12
10 15
1 3
1 15
6 11
6 8
6 14
7 13
3 9
3 6
12 15
3 12
4 11
5 9
14 15
3 15
8 11
5 12
9 10
5 15
10 11
9 13
1 5
10 14
11 13
1 11
1 8
1 14
2 13
7 9
6 13
7 12
6 10
7 15
12 14
3 11
3 5
4 10
4 13
5 8
9 12
8 10
10 13
1 4
2 3
2 9
1 7
11 12
2 6
2 12
1 13
9 15
2 15
13 15
7 11
7 8
7 14

输出样例 #3

27077

数据范围

每组测试数据的第一行包含两个整数 $n,m$（$1\le n\le 100000$，$0\le m\le 1000000$），分别表示城市数量和道路数量。

第 $i$ 行给出城市 $i$ 的净收益 $V_i$，满足 $0\le |V_i|\le 20000$。

（$1\le n\le 100000$，$0\le m\le 1000000$）