题目描述

工厂有 $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

样例输出

26

数据范围与提示

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