Background

Special for beginners, ^_^

Description

小 A 有 N(1 <= N <= 10,000)头奶牛，每头奶牛有个挤奶的时间；且某两头奶牛有 挤奶顺序，即：x y ，则只有在奶牛 x 挤完奶时，才能挤奶牛 y。现在给定 N 头奶牛的挤 奶时间，及 M（1 <= M <= 50,000）对先后关系，求挤奶的最少时间。

Format

Input

第一行为两个空格隔开的整数 N 和 M。 以下 N 行，第 i+1 行表示第 i 头奶牛的挤奶时间； (1 <= T(i) <= 100,000) 以下 M 行，每行两个整数 x,y，表示奶牛 x 在奶牛 y 之前挤奶。保证关系无环，即保证有解。

Output

最少的挤奶时间。

Samples

3 1 
10 
5 
6 
3 2

11

Limitation

先挤奶牛 1 3，第 6 秒时，奶牛 3 挤完了；接着挤奶牛 1 2，第 10 秒时，奶牛 1 挤 完了，第 11 秒时，奶牛 2 也挤完了。 30%的数据，1 <= N <= 100,1 <= M <= 50 100%的数据，1 <= N <=10000,1 <= M <= 50000