You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

Fife 正在玩一个游戏。游戏一共有 n 个任务，目标是完成第 n 个任务。每当你完成了 某个任务，就可以解锁一些后面的任务中任意一个（但只能解锁一个）。一开始只有 1 号任务可以完成。只有已经解锁了的任务才能完成。

每个任务都有一个难度值。为了减小极端数据的影响，最后游戏的得分就是所有 Fife完成的任务难度值的中位数。（如果完成了奇数个任务，中位数就是难度值排序后正中间的那个数；否则是中间的两个数中较大的那个）

Fife 已经事先知道了每个任务的难度值，以及任务之间的依赖关系，希望最后的得分尽量大。

【输入格式】

第 1 行输入两个正整数 n，m，表示任务个数和任务的依赖关系数。 第 2 行输入 n 个由空格隔开的整数 A[i],即第 i 个任务的难度值。 接下来 m 行，每行输入两个整数 x, y，表示完成第 x 个任务后就可以选择解锁第 y 个任务。

【输出格式】

输出一行一个正整数表示最大可能的得分。

【样例输入】

5 5
1 2 3 4 5
1 2
2 3
3 5
2 4
4 5

【样例输出】

4

【样例解释】

方案如下：依次完成任务 1，任务 2，任务 4，任务 5，难度值为{1,2,4,5}，中位数为 4。

【数据范围】

30% 的数据 ：n≤8, m≤20

50% 的数据 ：n≤40, m≤200

另外 20% 的数据完成第 i 个任务后只能解锁第 i+1 个任务

100% 的数据：n≤10,000, m≤100,000, 0≤A[i]≤1,000,000,000