题目描述

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

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

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

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

输入格式

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

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

接下来的 $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

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

输出样例 #2

7

输入样例 #3

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

输出样例 #3

7

数据范围

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

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