工作规划

题目描述

n 台机器人正在完成任务。其中，第 i 台机器人需要工作 t_i 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m条，每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。

请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。

输入格式

第一行：两个整数 n 和 m

第二行到第 n+1 行：每个机器人需要的时间 t_i

接下来 m 行：每行有两个整数 a 和 b，表示第 b 台机器人必须要等第 a 台机器人任务完成之后才能开始工作。

输出格式

单个整数，表示所有机器人任务完成最少需要花多少时间。

输入样例

10 9
3
29
1
35
18
22
8
29
4
12
3 2
4 8
1 7
6 5
7 10
8 1
10 9
2 4
5 3

输出样例

161

说明提示

1≤n≤10⁴，1≤m≤50,000，1≤t_i≤105，1≤a_i,b_i≤n