题目描述

小程有N头奶牛(1<=N<=10,000)，编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是，由于小程的仓库布局，一些奶牛要在别的牛之前挤奶。比如说，如果奶牛A必须在奶牛B前挤奶，小程就需要在给奶牛B挤奶前结束给奶牛A的挤奶。 为了尽量完成挤奶任务，小程聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请帮助小程计算挤奶过程中的最小总时间。

输入格式

两个空格分隔的整数：N（奶牛数量）和 M（挤奶限制数量；1 <= M <= 50,000）。 第 2~1+N 行共N行，第 i+1行为 T(i) 的值 (1 <= T(i) <= 100,000)。 第2+N~1+N+M行：每行包含两个空格分隔的整数A和B，表示奶牛A必须挤满奶才能开始挤奶牛B。这些约束永远不会形成循环，所以 解决办法总是可能的。

输出格式

一个整数表示对所有奶牛挤奶所需的最短时间。

3 1
10
5
6
3 2

11

数据规模与约定

【样例解释】 有3头牛。 每头奶牛挤奶所需的时间分别为 10、5 和 6。 必须先对奶牛 3 进行挤奶，然后才能开始对奶牛 2 进行挤奶。 奶牛 1 和奶牛 3 最初可以同时挤奶。 当奶牛 3 完成挤奶后，奶牛 2 就可以开始挤奶了。 经过 11 个单位时间后，所有奶牛都完成挤奶。