J14 习题-4 挤牛奶

题目描述

小 $void$ 有 $N$ 头奶牛，每头奶牛有个挤奶的时间；且某两头奶牛有挤奶顺序，即：$x\ y$，则只有在奶牛 $x$ 挤完奶时，才能挤奶牛 $y$。现在给定 $N$ 头奶牛的挤奶时间，及 $M$ 对先后关系，求 $N$ 头奶牛都挤完奶的最早时间。

输入格式

第一行为两个空格隔开的整数 $N$ 和 $M$ 。 以下 $N$ 行，第 $i+1$ 行表示第 $i$ 头奶牛的挤奶时间 $T_i$；

以下 $M$ 行，每行两个整数 $x,y$，表示奶牛 $x$ 在奶牛 $y$ 之前挤奶。保证关系无环，即保证有解。

输出格式

输出共一行一个整数 $Ret$，$N$ 头奶牛都挤完奶的最早时间。

样例输入

3 1
10
5 
6
3 2

样例输出

11

样例分析

先挤奶牛 $1$ 和 $3$，第 $6$ 秒时，奶牛 $3$ 挤完了；接着挤奶牛 $1$ 和 $2$，第 $10$ 秒时，奶牛 $1$ 挤完了，第 $11$ 秒时，奶牛 $2$ 也挤完了。

数据范围

对于 $30\%$ 的数据：$1\le N\le 100$，$1\le M\le 50$； 对于 $100\%$ 的数据：$1\le N\le 10,000$，$1\le M\le 50,000$, $1\le T_i\le 100,000$。