Hold off the enemy

The country of nein declared war on the country of sys. Between the two countries there are $n$ strongholds, and some pairs of strongholds are joined by roads. Once a stronghold falls, every stronghold joined to it by a road becomes the next target.

Each stronghold has a troop count that holds it for certain. If you station $a_i$ troops at stronghold $i$, that stronghold survives every attack. With fewer troops it falls.

The invasion starts at stronghold $n$, the capital of nein, and spreads through fallen strongholds. If it reaches stronghold $1$, the capital of sys, sys loses the war. Neither capital can be garrisoned.

Yeongseon, the king of sys, has $k$ troops. Decide whether he can distribute them among the strongholds so that the invasion never reaches stronghold $1$. The total number of troops stationed cannot exceed $k$.

The first line contains the number of strongholds $n$, the number of roads $m$, and the number of troops $k$. ($2 \le n \le 100$, $1 \le m \le 1000$, $1 \le k \le 10000$)

The second line contains $a_1, a_2, \dots, a_n$, where $a_i$ is the number of troops needed to hold stronghold $i$. ($1 \le a_i \le 1000$) Neither capital can be garrisoned, so $a_1$ and $a_n$ are always $-1$.

Each of the next $m$ lines contains the numbers $u$ and $v$ of the two strongholds joined by a road. ($1 \le u, v \le n$, $u \ne v$) Roads are bidirectional, and the same pair can appear more than once.

Print YES if $k$ troops can be placed so that the invasion is stopped, and NO otherwise.