题目描述

一轮正在玩杀戮尖塔，游戏的地图可以看成有 $n$ 个点和 $m$ 条边组成的有向无环图，一轮初始有 $x$ 点血量。

每个节点上都有一个事件，当一轮到达该节点时，会根据事件效果增加或减少一定血量。

一轮必须选择一个入度为零的节点作为起点，并到达一个出度为零的节点作为终点。

在行进过程中，如果一轮的血量在任何时刻小于等于 $0$ ，则一轮失败。一轮需要找到一条从起点到终点的路径，使得最终血量尽可能大。

请你计算一轮游戏结束时最多能有多少血量。如果不存在任何有效路径（即从任意起点出发都会中途死亡导致无法到达任何终点），则输出 $-1$ 。

输入格式

第一行包含三个整数 $n$, $m$, $x$，分别表示节点数、边数和初始血量。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$，其中 $h_i$ 表示第 $i$ 个节点的事件值（正数表示回血，负数表示扣血）。

接下来 $m$ 行，每行包含两个整数 $u_i$, $v_i$，表示一条从 $u_i$ 指向 $v_i$ 的有向边。数据保证图是有向无环图。

输出格式

输出一个整数，表示游戏结束时一轮的最大血量。如果不存在有效路径，输出 $-1$ 。

3 2 5
-10 -5 1
1 2
2 3

-1

解释 #1

很明显一轮只能进入节点 $1$ ，然后血量就归零了，所以输出 $-1$ 。

数据范围

$2 \le n \le 10^5$

$1 \le m \le 5\times 10^5$

$-10^9 \le h_i \le 10^9$

$1 \le x \le 10^9$