训练排程（schedule）

题目描述

$\text{DAMON THRONE}$ 的训练系统中有 $n$ 个学习任务。

第 $i$ 个任务需要花费 $t_i$ 天完成。

有些任务之间存在依赖关系。若存在一条依赖关系：

$$u \to v$$

表示任务 $u$ 必须在任务 $v$ 开始之前完成。

训练系统可以同时安排多个没有依赖冲突的任务。也就是说，只要一个任务的所有前置任务都已经完成，它就可以立刻开始。

请你求出完成所有任务至少需要多少天。

如果这些依赖关系存在矛盾，导致无法完成所有任务，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$，分别表示任务数量和依赖关系数量。

第二行包含 $n$ 个整数：

$$t_1,t_2,\ldots,t_n$$

表示每个任务需要花费的天数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示任务 $u$ 必须在任务 $v$ 之前完成。

输出格式

输出一行一个整数。

如果可以完成所有任务，输出完成所有任务至少需要多少天；否则输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

13

样例解释 #1

任务 $1$ 需要 $3$ 天，任务 $2$ 需要 $2$ 天。

任务 $3$ 必须等任务 $1$ 和任务 $2$ 都完成后才能开始，因此任务 $3$ 最早在第 $3$ 天后开始，完成时间为：

$$3+4=7$$

任务 $5$ 必须等任务 $2$ 完成后开始，完成时间为：

$$2+1=3$$

任务 $4$ 必须等任务 $3$ 和任务 $5$ 都完成后才能开始，因此任务 $4$ 最早在第 $7$ 天后开始，完成时间为：

$$7+6=13$$

所以完成所有任务至少需要 $13$ 天。

输入输出样例 #2

输入 #2

3 3
1 2 3
1 2
2 3
3 1

输出 #2

-1

样例解释 #2

任务之间形成了循环依赖：

$$1\to2\to3\to1$$

没有任何任务能够正常完成所有依赖，因此输出 $-1$。

数据范围与约定

对于所有测试数据，保证：

$$1 \le n \le 2\times 10^5,\quad 0 \le m \le 2\times 10^5,\quad 1 \le t_i \le 10^9 $$$$1 \le u,v \le n,\quad u\ne v$$

测试点	分值	$n$	$m$	$t_i$	特殊性质
$1\sim 2$	$10$	$\le 20$	$\le 100$		无
$3\sim 4$	$20$	$\le 2000$	$=0$	$\le 10^9$	$\text{A}$
$5\sim 6$			$\le 2000$		$\text{B}$
$7\sim 8$		$\le 10^5$			$\text{C}$
$9\sim 10$	$30$	$\le 2\times 10^5$			无

特殊性质 $\text{A}$：保证没有任何依赖关系。

特殊性质 $\text{B}$：保证所有依赖关系形如 $i\to i+1$，即任务构成一条链。

特殊性质 $\text{C}$：保证依赖关系中不存在循环。