적군을 막아라

nein나라가 sys나라에 전쟁을 일으켰다. 두 나라 사이에는 거점지 $n$개가 있고, 일부 거점지 쌍은 도로로 이어져 있다. 한 거점지가 뚫리면 그 거점지와 도로로 이어진 거점지가 다음 공격 대상이 된다.

거점지마다 공격을 확실히 막아내는 데 필요한 병력 수가 정해져 있다. 거점지 $i$에 병력 $a_i$명을 배치하면 그 거점지는 공격을 받아도 뚫리지 않는다. 그보다 적게 배치하면 뚫린다.

침공은 nein나라의 수도인 거점지 $n$에서 시작해 뚫린 거점지를 따라 번진다. 침공이 sys나라의 수도인 거점지 $1$까지 닿으면 sys나라는 전쟁에서 진다. 두 수도에는 병력을 배치할 수 없다.

sys나라의 왕 영선이는 병력 $k$명을 가지고 있다. 병력을 거점지에 나누어 배치해서 침공이 거점지 $1$에 닿지 않게 만들 수 있는지 판정하라. 배치한 병력의 합은 $k$를 넘을 수 없다.

첫째 줄에 거점지의 수 $n$, 도로의 수 $m$, 병력의 수 $k$가 주어진다. ($2 \le n \le 100$, $1 \le m \le 1000$, $1 \le k \le 10000$)

둘째 줄에 $a_1, a_2, \dots, a_n$이 주어진다. $a_i$는 거점지 $i$를 막는 데 필요한 병력 수다. ($1 \le a_i \le 1000$) 두 수도에는 병력을 배치할 수 없으므로 $a_1$과 $a_n$은 항상 $-1$이다.

다음 $m$개 줄에 도로가 잇는 두 거점지의 번호 $u$와 $v$가 주어진다. ($1 \le u, v \le n$, $u \ne v$) 도로는 양방향이고, 같은 쌍이 두 번 이상 주어질 수 있다.

병력 $k$명을 적절히 배치해서 침공을 막을 수 있으면 YES를, 막을 수 없으면 NO를 출력한다.