题目描述

在深海中有 $n$ 个信号站（编号 1~$n$），由 $m$ 条海底光缆连接（双向传输）。

每条光缆有信号衰减值 $d_i$。每经过一条光缆，信号强度减少 $d_i$。

每个中继站有一个维护等级 $c_i$。信号只能经过维护等级不超过 $X$ 的站点。站点本身不消耗信号，但信号经过站点必须满足 $c_i ≤ X$ 才能安全通过。

（起点 1 和终点 $n$ 也须满足 $c_i ≤ X$。）

信号从站点 1 出发，初始强度为 $P$，到达站点 $n$ 时强度必须 ≥ 0。

目标：求最小的 $X$，使得存在一条从 1 到 $n$ 的路径，满足：

1. 路径上所有站点的维护等级 $c_i ≤ X$；
2. 路径上所有光缆的衰减之和 $≤ P$（即衰减总和不超过初始信号）。

如果即使允许所有站点（$X = max (c_i)$），最短路衰减也超过 $P$，输出 -1。

输入格式

第一行三个整数 $n, m, P$（$P$ 为初始信号强度）。 第二行 $n$ 个整数 $c_1, c_2, ..., c_n$，表示各站点的维护等级。 接下来 $m$ 行，每行三个整数 $u, v, d$，表示一条光缆及其衰减值。

输出格式

一行一个整数，表示最小的 $X$。如果无法到达输出 -1。

样例

5 5 10
3 7 5 9 2
1 2 3
1 3 2
2 5 6
3 4 4
4 5 5

7

提示

样例解释

二分 $X=5$，允许站点 {1,3,5}。 从 1 出发只能到 3，从 3 到 4（但 4 的 c=9>5），无法到达 5。$X$=7 时允许 {1,2,3,5}，路径 1→2→5 衰减 3+6=9 ≤ 10，可行。故答案为 7。

数据范围

• $2 ≤ n ≤ 10^4，1 ≤ m ≤ 5×10^4$

• $1 ≤ c_i, d_i, P ≤ 10^9$

• 图为任意无向图