题目描述

暑假了，zyg来到了幻想乡，根据一般剧情，他首先要去的是红魔馆，而在去红魔馆的路上有一片雾之湖，里面住着冰之妖精琪露诺（也叫⑨），为了更快到达红魔馆，zyg想要横穿雾之湖，于是他请到了⑨来帮忙，⑨用她强大的力量将湖面的一些地方冻住，以供zyg站立，冻住的湖面总共有\(n\)块，第一块和第\(n\)块分别连着起点和终点的岸边，也就是说zyg要从第\(1\)块地方跳到第\(n\)块地方。其中有些冻住的湖面离得比较近，可以从一个地方跳到另一个地方（也就是存在路径），而且需要花费不同的时间。然而⑨并不能很好地控制自己的力量，有些地方冻得结实有些地方不结实，每块冻结的湖面可以用一个数来表示结实程度。zyg想要从\(1\)走到\(n\)有很多条路径，每条路径的安全系数\(q\)定义为该路径上冻结的湖面的结实程度的最小值。为了安全，zyg希望找到一条安全系数\(q\)最大的路径。同时，雾之湖上太冷，zyg也很怕冷，所以zyg还需要一定时间内通过雾之湖。

Format

输入数据

第一行 3 个正整数 \(n\),\(m\),\(b\)。分别表示有\(n\)块冻住的湖面，\(m\)条路径，以及 zyg 需要在时间\(b\)内通过雾之湖(等于也可)。其中zyg需要从第\(1\)块跳到第\(n\)块，从岸上跳到第\(1\)块及第\(n\)块跳到岸上时间忽略不计。接下来\(n\)行，每行一个正整数\(f_i\)，表示第\(i\)块湖面的结实程度是\(f_i\)。 再接下来有\(m\)行，每行三个正整数 \(a_i\)，\(b_i\)，\(c_i\)（\(1 \leq a_i,b_i \leq n\)）。表示第\(a_i\)块冻住的湖面 可以跳到第\(b_i\)块冻住的湖面，或者反过来，都需要消耗\(c_i\)的时间。

输出数据

仅一个正整数，表示zyg通过雾之湖路径上安全系数\(q\)的最大值。如果他无法通过雾之湖，请输出NO。

Sample 1

Input

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

Output

6

Limitation

1s, 256MiB for each test case.

Hint

样例解释

选择 1—3—4 的路径，安全系数为\(6\)，而 1—2—4 的路径，安全系数则为\(5\)，故选择前者更优，输出\(6\)。两种路径均可以在规定时间内通过雾之湖。

数据规模

对于 60%的数据，满足 \(n≤200\)，\(m≤10000\)，\(b≤200\)；
对于 100%的数据，满足 \(n≤10000\)，\(m≤50000\)，\(b≤1000000000\)；
对于 100%的数据，满足 \(c_i≤1000000000\)，\(f_i≤1000000000\)，可能有两条路径连接着相同的湖面。

其它

zyg 是你们的学长，请尽力帮助他。

Source

8月24日 夏日大礼包