Background

我举杯将「虚无」驱散——海列屈拉

愿「海洋」奏响欢宴

Description

众所周知，海列屈拉的预言和凯撒是一样的。

这天，凯撒交给海瑟音了一个任务，这个任务有 $N$ 个模块，编号 $1$ 到 $N$，其中模块 $i$ 需要花费 $W_i$ 的时间完成，当所有模块都完成时任务完成，凯撒要求她在 $T$ 时间内完成任务。

模块之间有 $M$ 个依赖关系，模块 $V$ 依赖模块 $U$ 表示模块 $V$ 需要在模块 $U$ 完成之后才可开始，互不依赖的模块可以同时开始。

作为大海的女儿，她可以召唤 $X$ 个帮手和她一起完成任务，当一个模块需要的时间 $W_i \le X$ 时，该模块会立刻完成，耗时为 $0$，而对于 $W_i > X$ 的情况，耗时不变。

她想知道在 $T$ 时间内完成任务的情况下，最少需要多少个帮手。

Format

Input

第一行输入三个空格分隔的整数 $N, M, T \ (1 \le N, M \le 5 \times 10^4, \ 0 \le T \le 2 \times 10^9)$，分别表示模块总数、依赖关系数和时间限制。

第二行输入 $N$ 个空格分隔的整数 $W_i \ (1\le i\le N, 0 \le W_i \le 10^9)$，表示每个模块需要的时间。

接下来 $M$ 行每行输入两个空格分隔的整数 $U_j, V_j \ (1\le j\le M, 1 \le U, V \le N, \ U \ne V)$，表示模块 $V_j$ 依赖模块 $U_j$。

Output

输出一个整数，表示她需要的帮手数量 $X$ 的最小值。

Samples

4 3 25
10 20 15 10
1 2
2 3
1 4

15