J. Colossal Cash
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are N barns, labeled from $$$1$$$ to $$$N$$$, and $$$M$$$ one directional roads that connect two barns. Every time Joe visits a barn $$$i$$$, he obtains exactly $$$c_i$$$ Cow Credits™, and every time Joe takes a specific road $$$j$$$, he loses exactly $$$c_j$$$ Cow Credits™. Joe has also developed a teleporter that can instantly take him from any barn he is in (barn $$$a$$$) to any barn $$$b$$$ at any time, at the cost of $$$K \cdot |a-b|$$$ Cow Credits™. If Joe teleports to a barn, he will still receive the $$$c_i$$$ Cow Credits™. Joe wants you to tell him if it is possible to create a cycle of traveling or teleporting to barns such that he infinitely gains Cow Credits™.

Input

Line $$$1$$$: Three space separated integers $$$N$$$ ($$$1 \le N \le 500$$$), $$$M$$$ ($$$1 \le M \le 5 \times 10^3$$$), and $$$K$$$ ($$$1 \le K \le 10^3$$$).

Line $$$2...N+1$$$: An integer representing $$$c_i$$$ ($$$1 \le c_i \le 10^5$$$).

Lines $$$N+2...M+N+1$$$: Three space separated integers $$$a_j$$$, $$$b_j$$$ ($$$0 \le a_j, b_j, \le N$$$), and $$$c_j$$$ ($$$0 \le c_j \le 10^5$$$).

Output

Line $$$1$$$: Print either $$$YES$$$ if it possible to form a cycle or $$$NO$$$ if it isn't.

Example
Input
3 2 10
3
8
20
1 2 4
3 1 16
Output
YES
Note

$$$1 \le N \le 500$$$

$$$1 \le M \le 5 \times 10^3$$$

$$$1 \le K \le 10^3$$$

Assume that Joe can temporarily go negative in Cow Credits™ as long as he makes a net profit.