当前没有测试数据。

题目描述

工厂有 $N$ 个零件需要加工，零件编号为 $1 \sim N$ ，编号为 $i$ 的零件加工需要的时间为 $T_i$ 。

某零件加工时，需要使用其他的零件，因此需要等待其所依赖的零件加工完，该零件才能加工。

比如， $X$ 零件依赖 $Y,Z$ 两个零件， $Y$ 零件依赖 $Z$ 零件，那么必须先生产 $Z$ 零件，再产生 $Y$ 零件，最后生产 $X$ 零件。

工厂有足够的加工师傅，只要某零件可以加工（其所依赖的零件已经加工完毕），会立刻有师傅来加工该零件，加工不同零件切换过程不消耗时间。

请编程计算出，所有的零件加工完，最短需要多长时间。

输入

第 $1$ 行读入 $N,M$ ，表示需要加工的零件数量和零件之间依赖关系的数量。

接下来 $N$ 行，依次读入每个零件加工所需要的时间。

接下来 $M$ 行，每行有 $2$ 个整数 $X_i,Y_i$ ，表示编号为 $Y_i$ 的零件加工，需要依赖编号为 $X_i$ 的零件。

数据保证不会出现环形依赖关系。

输出

输出所有零件加工完毕的最少时间。

样例

5 1
10
20
30
40
50
2 4

60

5 3
10
8
16
9
4
1 2
2 3
1 3

34

数据范围

对于 $100\%$ 的数据， $1 \le N \le 10^4$ ， $1 \le M \le 5 \times 10^4$ ， $1 \le T_i \le 10^5$ ， $1 \le X_i,Y_i \le N$ 。