Description

huhe在内蒙养了N头奶牛，他一回到家就要给这些奶牛挤奶，每头牛的个性不一样，有的看见huhe就跑。经过长时间的观察，他计算出每头奶牛的挤奶时间；且某两头奶牛有挤奶顺序，即：xy，则只有在奶牛x挤完奶时，才能挤奶牛y。按照他算好的N头奶牛的挤奶时间，及M对先后关系，求huhe能搞定所有奶牛的最早时间。

Format

Input

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

Output

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

Samples

3 1
10
5
6
3 2

11

TIPS

【样例解释】 先挤奶牛1和3，第6秒时，奶牛3挤完了；接着挤奶牛1和2，第10秒时，奶牛1挤完了，第11秒时，奶牛2也挤完了。 【数据规模】 对于30%的数据：1≤N≤100；1≤M≤50； 对于100%的数据：1≤N≤10,000；1≤M≤50,000；1≤T_i≤100,000；